# String Split + Dynamic Programming

leetcode problem 140: Word Break II

給定一個字串，並用一個給定的dictionary切割此字串，輸出所有的切割方法。
例:
Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

## 解
沿用上例，直接以圖說明。

最後得到的dp一維陣列就是所有切割點。接著用遞迴backtracking方式由後往前找，就能找出所有切割方法。

## Code
leetcode problem 140

class Solution {
public:
    vector<int> index;
    vector<string> ans;
    int len = 0;
    void breakdown(string s, string res, set<string>& words, int ind){
        if(ind == 0){
            if(res.size() - count(res.begin(), res.end(), ' ') == len){
                res.erase(res.begin()+res.size()-1);
                ans.push_back(res);
            }
            return;
        }
        
        for(int i=ind;i>0;i--){
            for(int j=i-1;j>=0;j--){
                int len = index[i] - index[j];
                string sub = s.substr(index[j]+1,len);
                if(words.count(sub)){
                    string tmp = (sub + " " + res);
                    breakdown(s, tmp, words, j);
                }
            }
        }
    }
    
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        string origin = " " + s;
        set<string> words;
        len = s.size();
        int dp[len+1];
        for(int i=0;i<len+1;++i){
            dp[i]=0;
        }
        dp[0]=1;
        for(int i=0;i<wordDict.size();++i){
            words.insert(wordDict[i]);
        }
        index.push_back(0);
        for(int i=0;i<len+1;i++){
            for(int j=0;j<i;j++){
                if(words.count(s.substr(j,i-j)) && dp[j]){
                    dp[i]=1;
                    index.push_back(i);
                    break;
                }
            }
        }
        breakdown(origin, "", words, index.size()-1);
        return ans;
    }
};