Word Break II .3.cpp

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<vector<int>>dp(s.size()+1,vector<int>());
        dp[0].push_back(0);
        for(int i=1;i<=s.size();i++){
            for(int j=1;j<=i;j++)
                if(!dp[j-1].empty() && dict.count(s.substr(j-1,i-j+1))!=0)
                    dp[i].push_back(j);
        }
        vector<string>ret;
        vector<string>tmp;
        dfs(ret,tmp,dp,s,dp.size()-1);
        return ret;
    }
    void dfs(vector<string>&ret,vector<string>&tmp,vector<vector<int>>&dp,string &s,int cur){
        if(cur==0){
            string str=tmp.back();
            for(int i=tmp.size()-2;i>=0;i--)
                str=str+" "+tmp[i];
            ret.push_back(str);
        }else{
            for(int i=0;i<dp[cur].size();i++){
                int j=dp[cur][i];
                tmp.push_back(s.substr(j-1,cur-j+1));
                dfs(ret,tmp,dp,s,j-1);
                tmp.pop_back();
            }
        }
    }
};