Word Break I & II (Leetcode 139,

Word Break I
https://leetcode.com/problems/word-break/

Word Break I 中，要点是该如何节省时间。我们找到wordDict 中最长单词的长度， 然后让 j 从后往前loop，当loop到最长长度时就停止 (因为后面不会再有合适的单词了)。

bool wordBreak(string s, unordered_set<string>& wordDict) {
        if(wordDict.empty()) return false;
        int len = s.length();
        int max_len = 0;
        for(string it : wordDict){
            max_len = max(max_len, (int)it.length());
        }
        vector<int> dp(len+1, false);
        dp[0] = true;
        for(int i=0; i<s.length(); i++){
            int idx = max(0, i-max_len);
            for(int j=i; j >= idx; j--){
                if(!dp[j]) continue;
                string cur = s.substr(j, i-j+1);
                if(wordDict.count(cur)){
                    dp[i+1] = true;
                }
            }
        }
        return dp[len];
    }

Word Break II
https://leetcode.com/problems/word-break-ii/

Word Break II 中重点是prunning，如果第一次DFS search时，该string不能够被break，则以后的DFS需要跳过该string。比如:

string = aaabaaa
dict = ["a", "aa", "aaa"]

在DFS "a"的时候，可以意识到 substring "aaabaaa" 是invalid的，所以在search "aa" 的时候，应当跳过 substring "aaabaaa"。

利用一个vector<bool> 来记录 substring (i+1, n) 是否breakable。

class Solution {
public:
    
    void findcombo(vector<string> &allcomb, vector<string> &comb, vector<bool> &breakable, unordered_set<string>& wordDict, string s, int start){
        if(start == s.length()){
            //if(comb.empty()) return;
            string ret = comb[0];
            for(int i=1; i<comb.size(); i++){
                ret += " " + comb[i];
            }
            allcomb.push_back(ret);
            return;
        }
        
        for(int i=start; i<s.length(); i++){
            if(!breakable[i+1]) continue;
            string cur = s.substr(start, i-start+1);
            if(!wordDict.count(cur)) continue;
            comb.push_back(cur);
            int size = allcomb.size();
            findcombo(allcomb, comb, breakable, wordDict, s, i+1);
            comb.pop_back();
            if(allcomb.size() == size) breakable[i+1] = false;
        }
    }

    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        vector<string> allcomb;
        if(wordDict.empty()) return allcomb;
        vector<string> comb;
        int len = s.length();
        vector<bool> breakable(len+1, true);
        findcombo(allcomb, comb, breakable, wordDict, s, 0);
        return allcomb;
    }
};