140. word break ii

139. Word Break https://leetcode.com/problems/word-break/
     140.word break ii https://leetcode.com/problems/word-break-ii/
     dfs剪枝，带一点dp的感觉。

1.流传最广的方法，先用DP判断是否可以进行分割，再用dfs遍历方案：

class Solution {
public:
    string m_str;
    unordered_set<string> m_wordDict;
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        m_str = s;
        m_wordDict = wordDict;
        string now = "";
        vector<string> result;
        result.clear();
        
        int n = s.length();
        int dictsize = wordDict.size();
        if(dictsize == 0) {
            return result;
        }
        if(n == 0) {
            result.push_back("");
            return result;
        }
        
        bool f[n + 1];
        f[0] = true;
        for(int i = 1; i <= n; i++) {
            f[i] = false;
            for(int j = 0; j < i; j++) {
                if(f[j] && wordDict.find(s.substr(j,i-j))!=wordDict.end()) {
                    f[i] = true;
                    break;
                }
            }
        }
        if(f[n] == false) {
            return result;
        }
        
        wordBreakRecursion(result, now, f, 1);
        return result;
    }
    
    void wordBreakRecursion(vector<string>& result, string now, bool * f,int charnum){
        if(charnum == m_str.length() + 1){
            now = now.substr(0, now.length() - 1);
            result.push_back(now);
            return;
        }
        for(int i = charnum; i <= m_str.length(); i++) {
            //cout<<"f["<<i<<"]="<<f[i]<<" charnum="<<charnum<<endl;
            if(f[i] == true && m_wordDict.find(m_str.substr(charnum - 1, i - charnum + 1))!=m_wordDict.end()) {
                now += m_str.substr(charnum - 1, i - charnum + 1);
                now += " ";
                //cout<<"now = ["<<now<<"]"<<endl;
                wordBreakRecursion(result, now, f, i + 1);
                now = now.substr(0, now.length() - i + charnum - 2);
            }
        }
    }
};

2.纯dfs，会time limit exceeded

class Solution {
    void helper(vector<string> &res, string now, string & s, int pos, unordered_set<string>& wordDict) {
        if(pos == s.size()) {
            res.push_back(now.substr(1));
            return;
        }
        for(int i = pos; i < s.size(); i++) {
            string sub = s.substr(pos,i - pos + 1);
            if(wordDict.find(sub) != wordDict.end()) {
                helper(res,now + " " + sub,s,i+1,wordDict);
            }
        }
    }
public:
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        vector<string> res;
        helper(res,"",s,0,wordDict);
        return res;
    }
};

3.纯dp，会memory limit exceeded

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        int n = s.size();
        vector<bool> dp(n+1,false);
        vector<vector<string> > res(n+1,vector<string>());
        dp[0] = true;
        res[0].push_back("");
        for(int i = 0; i < n; i++) {
            for(int j = 0; j <= i; j++) {
                string t = s.substr(j, i - j + 1);
                if(dp[j] && wordDict.find(t) != wordDict.end()) {
                    dp[i+1] = true;
                    for(int k = 0; k < res[j].size(); k++)
                        res[i+1].push_back(res[j][k] + " " + t);
                }
            }
        }
        for(int k = 0; k < res[n].size(); k++) {
            res[n][k] = res[n][k].substr(1);
        }
        return res[n];
    }
};    

4.discuss里的解法，带剪枝的dfs，我没明白它和dp方法用的内存区别在哪儿，等我想一下。
想明白了，这个是要dfs到最后发现可以生成一个新组合才把一个word放在mem里，而我的dp是从前往后，不会到达最后一点的word也都加入到了mem里，所以超了。

class Solution {
    vector<vector<string>> mem;
    vector<int> visit;
    void DFS(string& s, unordered_set<string>& wordDict, int pos) {
        visit[pos] = 1;
        for (int i = pos + 1; i <= s.size(); ++i) {
            if (wordDict.find(s.substr(pos, i - pos)) != wordDict.end()) {
                if (i == s.size()) {
                    mem[pos].push_back(s.substr(pos, i - pos));
                    continue;
                }
                if (!visit[i])
                    DFS(s, wordDict, i);
                for (auto& str : mem[i]) 
                    mem[pos].push_back(s.substr(pos, i - pos) + " " + str);
            }
        }
    }

public:
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        visit.resize(s.size());
        mem.resize(s.size());
        DFS(s, wordDict, 0);
        vector<string> answ = mem[0];
        mem.clear();
        visit.clear();
        return answ;
    }
};