140. Word Break II -----H

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. Return all such possible sentences.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

Example 2:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

---

A:

----------------就是简单的 DP-------------

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> S(wordDict.begin(), wordDict.end());
        int maxWordLen = 0;
        for (auto s : wordDict) {
            maxWordLen = max(maxWordLen, (int)s.length());
        }
        
        unordered_map<int, vector<string>> map;
        for(int end =0; end<s.length(); end++){
            for(int start = max(0,end-maxWordLen+1); start<=end;start++){
                string curStr = s.substr(start, end-start+1);
                if(S.find(curStr) != S.end()){ //  find current substring
                    if(start == 0){
                        map[end].push_back(curStr);
                    }else if(map[start-1].size()>0){
                        for(auto s:map[start-1])
                            map[end].push_back(s +" "+curStr);
                    }
                }
            }
        }
        return map[s.length()-1];
    }
};

然而LTE了。进一步的改进是减少中间的存储内容。每次，只是保存前面substring的index

这种分治的问题，都最终能转成动态规划，所以先写了动态规划的思路，想直接一步到位，没想到反而遇到了问题，很有意思，哈哈。原因就是你求子问题的代价很大，而动态规划就是要求所有的子问题。而解决最终问题的时候，一些子问题其实是没有必要的。

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> S(wordDict.begin(), wordDict.end());
        int maxWordLen = 0;
        for (auto s : wordDict)
            maxWordLen = max(maxWordLen, (int)s.length());

        unordered_map<int, vector<int>> map;
        for (int end = 0; end < s.length(); end++) {
            for (int start = max(0, end - maxWordLen + 1); start <= end; start++) {
                if (S.find(s.substr(start, end - start + 1)) != S.end() && (start == 0 || map[start - 1].size() > 0))
                    map[end].push_back(start - 1);
            }
        }
        return buildResult(s, s.length() - 1, map);
    }
private:
    vector<string> buildResult(string s, int endIndex, unordered_map<int, vector<int>>& map) {
        vector<string> res;
        for (auto preEndIndex : map[endIndex]) {
            if (preEndIndex == -1) {
                res.push_back(s.substr(0, endIndex+1));
            }
            else {
                vector<string> preRes = buildResult(s, preEndIndex, map);
                for (auto pre : preRes)
                    res.push_back(pre + " " + s.substr(preEndIndex + 1, endIndex - preEndIndex));
            }
        }
        return res;
    }
};

****************************4th pass*************************************

public class Solution {
    public List<String> wordBreak(String s, Set<String> dict) {  
        if(s == null || s.length()==0)
            return new LinkedList<String>();
        
        List<List<Integer>> all = new LinkedList();// for every position         
        for(int i =0;i<s.length();i++){
            List<Integer> curList = new LinkedList();
            for(int j =i;j>=0;j--){
                if( dict.contains(s.substring(j,i+1)) && (j==0 || all.get(j-1).size()>0 ))
                    curList.add(j); //j is the starting point
            }
            all.add(curList);        
        }
        return bfs(all,s,s.length()-1 );
    }
    private List<String> bfs( List<List<Integer>> all, String s, int end){ 
        List<String> list = new LinkedList();
       if(end < 0){
           list.add("");
           return list;
        }
        for( int i : all.get(end)){
               List<String> pre = bfs(all,s,i-1);
               for(String str:pre)
                   list.add( new String(str + " " + s.substring(i,end+1) ).trim());
        }
        return list;            
    }
}

Error :
1:  one stupid problem is that, when writing the list[end].get(i) at line 25, I mistakenly write it as list[end].indexOf(i);   which is really cost me an hour in Leetcode , damn it
2:  for 100 days without coding, I even forget that  the generic types should be clearly set in the the function declaration.
     Like:  in the buildList() 
***************************************