题目描述

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

样例

输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
  "cats and dog",
  "cat sand dog"
]

算法1

(暴力枚举) $O(n^2)$

可以直接搜索，并且同时判断；
或者先判断，如果不能出现至少一条的话，直接返回空

算法2

记忆化搜索

从index往后的子串可以有多少中办法。。。

时间复杂度

参考文献

java 代码

class Solution {
       static List<String> ans = new ArrayList<String>();
    static HashSet<String> set = new HashSet<String>();
    static HashMap map=new HashMap<Integer,List<String>>();
    static  int n;
    //用以构造子串i-...的List<String>
    List<String> dfs(int index,String s){
        if(map.containsKey(index)) return (List<String>)map.get(index);
        List<String> res=new ArrayList<>();
        for(int i=index+1;i<=n+1;i++){
String sub=s.substring(index,i);
            if(set.contains(sub)){
                  if(i==n+1)
                  {
                      res.add(sub);
                  }
                else {
              List<String > next=dfs(i,s);
                for(String str:next){
                    res.add(sub+" "+str);
                }

            }
            }

        }

        map.put(index,res);
        return res;

    }
    public List<String> wordBreak(String s, List<String> wordDict) {
        ans.clear();
        set.clear();
        map.clear();
        n=s.length();
        s=" "+s;
         for(String t : wordDict)    set.add(t);
        return dfs(1,s);
    }
}