139. 单词拆分

不会

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        // dp[i] -> 长度为i的字符串是否可以拼出来
        // dp[j] = true if dp[j-i] == true and [i:j] in wordDict
        unordered_set<string> wordSet(wordDict.begin(),wordDict.end());
        vector<bool>dp(s.size()+1,false);
        dp[0]=true;
        for (int i = 1 ; i<=s.size();i++) {
            for (int j = 0; j < i; j ++ ) {
                string word = s.substr(j,i-j);
                if (dp[j] && wordSet.find(word)!= wordSet.end())
                    dp[i] = true;
            }
        }
        return dp[s.size()];
    }
};