139. 单词拆分

Problem: 139. 单词拆分

Code

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        //将单词划分 如果 0-j 和 j-i部分都可以在wordDict中找到
        //那么长度为i的字符串可以由wordDic拼接而成
        //dp[i] 表示长度为i的字符串可以由wordDic拼接而成
        unordered_set<string> set(wordDict.begin(),wordDict.end());
        vector<bool> dp(s.size()+1);
        dp[0]=true;
        for(int i=1;i<s.size()+1;i++) {
            for(int j=0;j<i;j++) {//用j去划分成两部分
                string sub = s.substr(j,i-j);//后面部分 s[j: i-1]
                if(set.find(sub)!=set.end()&&dp[j]) {//前面部分 s[0: j]
                    dp[i]=true;
                    break; // dp[i] = true了，i长度的子串已经可以拆成单词了，不需要j继续划分子串了
                }
            }
        }
        return dp[s.size()];
    }
};