Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].
对于brute force解法，代码比较简单，每次维护一个当前结果集，然后遍历剩下的所有子串，如果子串在字典中出现，则保存一下结果，并放入下一层递归剩下的字符。思路接近于我们在N-Queens这些NP问题中经常用到的套路。给个指针，前面部分在字典中，就将其添加到字符串后，然后递归计算后半部分。
public ArrayList<String> wordBreak(String s, Set<String> dict) {
ArrayList<String> res = new ArrayList<String>();
if(s==null || s.length()==0)
return res;
helper(s,dict,0,"",res);
return res;
}
//在s中，从start开始到最后的子串的切分。
private void helper(String s, Set<String> dict, int start, String item, ArrayList<String> res)
{
if(start>=s.length())
{
res.add(item);
return;
}
StringBuilder str = new StringBuilder();
for(int i=start;i<s.length();i++)
{
str.append(s.charAt(i)); //这里可以用substring(start,i+1)
if(dict.contains(str.toString())) //前面部分包含，则递归判断后面部分
{
//将前面部分添加到字符串后面。这里使用新串，是为了返回进行遍历i+1的时候不用删除前面添加的内容
String newItem = item.length()>0?(item+" "+str.toString()):str.toString();
helper(s,dict,i+1,newItem,res);
}
}
}
上面这个代码是可以，但是会出现重复计算结果集。
为了加快DFS的速度，我们应该添加记忆，也就是说，算过的字符串不要再重复计算。举例子：
apple n feng
app len feng
如果存在以上2种划分，那么feng这个字符串会被反复计算，在这里至少计算了2次。我们使用一个Hashmap把对应字符串的解记下来，这样就能避免重复的计算。 否则这一道题目会超时。
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
//使用map存放每个子串对应的所有结果集，这样防止出现重复计算导致超时。因为如上面dog，会计算两遍结果集
HashMap<String,List<String>> map=new HashMap<String,List<String>>();
if(s==null||s.length()==0||wordDict==null) return null;
return helper(map,s,wordDict);
}
//字符串str能够切分得到的结果集
public List<String> helper(HashMap<String,List<String>> map,String str,List<String> wordDict){
if(map.containsKey(str)){//该字符串的结果集已经有了
return map.get(str);
}
List<String> list=new ArrayList<>();//存放当前字符串的结果集
int len=str.length();
if(len==0){
list.add(""); //""在list中也占一个长度。
}else{
for(int i=1;i<=len;i++){
String sub=str.substring(0,i);
if(!wordDict.contains(sub)) continue;
//包含前面部分，这时求出后半部分的结果集。。如果i==len此时结果集中为""。长度为1.不是0
List<String> rightList=helper(map,str.substring(i,len),wordDict);
if(rightList.size()==0) continue;
for(String ss:rightList){
StringBuilder sb=new StringBuilder();
sb.append(sub);
if(i!=0&&i!=len){//i==len时，整个字符串在字典中，直接添加整个字符串就行，不需要空格，此时ss==""。
sb.append(" ");
}
sb.append(ss);
list.add(sb.toString());
}
}
}
map.put(str,list);
return list;
}
}