140. Word Break II

11194 단어 LeetCodeAC 코드
dp+dfs
class Solution {
public:
   void dfs(vector<string>&res,vector<bool>&dp,vector<vector<bool>>p,string s,string temp_s,int index){
        if(index==s.length()){
            
            res.push_back(temp_s);
            return;
        }
        for(int i=index;i<s.length();++i){
            if(dp[i+1]==0||p[index][i]==0)continue;
            string str=s.substr(index,i-index+1);
            if(!temp_s.empty())str=" "+str;
            dfs(res,dp,p,s,temp_s+str,i+1);
        }
    }
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        int n=s.length();
        vector<string>res;
        vector<bool>dp(n,false);
        vector<vector<bool>>p(n,vector<bool>(n,false));
        dp[0]=true;
        p[0][0]=true;
        for(int i=0;i<n;++i){
            for(int j=i;j>=0;--j){
                string str=s.substr(j,i-j+1);
                int t=count(wordDict.begin(),wordDict.end(),str);
                if(t&&dp[j]){
                    p[j][i]=true;
                    dp[i+1]=true;
                }
            }
        }
        if(dp[n])
            dfs(res,dp,p,s,"",0);
        return res;
    }
};

좋은 웹페이지 즐겨찾기