word break II(单词切分)

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"].

Word Break(动态规划)

对于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;
    }
}