140. Word Break II (String; DP)

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        results.clear();
        if(s.size() < 1 || wordDict.empty()) return results; 
        
        vector<vector<bool>> flag(s.length(),vector<bool>(s.length()+1, false)); //string, started from i with length j, can be found at least one form in the dict
        string str;
        
        for(int l = 1; l <= s.length();l++) //先把l小的处理完，有利于第三个for循环的判断
        {
            for (int i = 0; i <= s.length()-l; i++)
            {
                str = s.substr(i,l);
                if(wordDict.find(str)!=wordDict.end()) //find one form in dict
                {
                    flag[i][l] = true;
                    continue;
                }
                
                for(int k = 1; k < l; k++){ //check string started from i with length l can be divided by the words in dict 
                    if(flag[i][k] && flag[i+k][l-k]){
                        flag[i][l] = true;
                        break;
                    }
                }
            }
        }
        if (!flag[0][s.length()]) {
             return results;
         }
        
        string pre = "";
        dfs(s,pre, flag, wordDict, 0);
        return results;
    }
    void dfs(string &s, string pre, vector<vector<bool>> &dp, unordered_set<string> &dict, int start)
    {
        if(start == s.length())
        {
            results.push_back(pre);
            return;
        }
        string backup = pre;
        string tmp;
        for(int i = 1; i <= s.length()-start;i++)
        {
            if(!dp[start][i]) continue;
            tmp = s.substr(start, i);
            if (dict.find(tmp)==dict.end()) continue;
            if(pre=="") pre += tmp;
            else pre = pre + " " + tmp;
            dfs(s, pre, dp, dict, start+i);
            pre = backup; //backtracking
        }
    }
private: 
    vector<string> results;
};