Leetcode---Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Have you been asked this question in an interview?

首先思考能不能用卡特兰数思路来做，后来发现不行，因为这样会导致大量的重复。比如catsanddog，
f("cat")*f("sanddog")的解空间就和f("catsand")*f("dog")重复，都有解"cat sand dog"。

所以思考去掉重复，假设s[i,j]是从位置i到位置j的s的子字符串，0<=i<=j<=s.size()-1;
又假设f(s, i, j)是s[i, j]为输入的解空间，那么
f(s, i, j)=西格玛（s[i,k]*f(s,k+1,j)）,i<=k
这里的s[i,k]*f(s,k+1,j)指的是s[i,k]和f(s,k+1,j)解空间的每一个字符串相连接。
code如下：

bool contain(unordered_set<string> &dict, string s)
    {
        unordered_set<string>::iterator ite = dict.find(s);
        if(ite != dict.end())
            return true;
     else
            return false;
    }
    vector<string> f(string s, unordered_set<string> &dict, int a, int b,vector<vector<bool>>& dp){
        vector<string> result;
        if(dp[a][b]){
        if(contain(dict, s.substr(a,b-a+1))){
            result.push_back(s.substr(a,b-a+1));
        }
        for(int k=a;k<b;k++){
            if(contain(dict, s.substr(a,k-a+1)) && dp[k+1][b]){
            vector<string> right=f(s,dict,k+1,b,dp);
                for(int j=0;j<right.size();j++){
                        string tmp=s.substr(a,k-a+1)+" "+right[j];
                        result.push_back(tmp);
                }
            }
        }
        }
        return result;
    }
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));
        for(int i=0;i<s.size();i++){
            for(int j=i;j<s.size();j++){
                if(contain(dict,s.substr(i,j-i+1)))
                    dp[i][j]=true;

            }
        }
        for(int i=0;i<s.size();i++){
            for(int j=i;j<s.size();j++){
                if(dp[i][j]==false){
                for(int k=i;k<j;k++){
                    if(dp[i][k]&&dp[k+1][j]){
                        dp[i][j]=true;
                        break;
                    }
                }
            }
        }
        }
        return f(s,dict,0,s.length()-1,dp);
    }