Участник:Rashit/Word Break II

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/word-break-ii

 
class Solution {
 
    public:
    unordered_set<string> slova;
    vector<string> ans;
     void func(string& s,string temp,int x,vector<vector<pair<int,int>>>& dp){
        if(x==0){
            ans.push_back(temp);return;
        }
        for(int i=0;i<dp[x].size();i++){
            string v = s.substr(dp[x][i].first-1,dp[x][i].second-dp[x][i].first+1) + ' ' + temp;
            func(s,v,dp[x][i].first-1,dp);
        }
        return;
    }
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        for(auto i:wordDict)
            slova.insert(i);
        int n = s.size();
        vector<vector<pair<int,int>>> dp(n+1);
        dp[0].push_back({0,0});
        for(int i=1;i<=n;i++){
            string temp;
            if(dp[i-1].size()==0) continue;
            for(int j=i;j<=n;j++){
                temp.push_back(s[j-1]);
                if(slova.find(temp)!=slova.end()){
                    dp[j].push_back({i,j});
                }
            }
        }
        for(int i=0;i<dp[n].size();i++){
            string temp = s.substr(dp[n][i].first-1,dp[n][i].second-dp[n][i].first+1);
            func(s,temp,dp[n][i].first-1,dp);
        }
        return ans;
    }
};