139. 单词拆分

139. 单词拆分

动态规划

dp[i]表示s[0~i-1]能否用字典拼接出来。

第一个for：计算dp[i]的时候检验加入s[i-1]是否合法
第二个for：拆分成s[0~j-1]和s[j~i-1]两段，如果存在合法的可能，就说明加入s[i-1]是合法的，dp[i]=true;

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        auto wordSet=set<string>();
        for(auto word:wordDict){
            wordSet.insert(word);
        }
        
        auto dp=vector<int>(s.size()+1);
        dp[0]=true;
        
        for(int i=1;i<=s.size();i++){
            for(int j=0;j<i;j++){
                if(dp[j] && wordSet.find(s.substr(j,i-j))!=wordSet.end()){
                    dp[i]=true;
                    break;
                }
            }
        }
        
        return dp[s.size()];
    }
};