139.单词拆分

思路：这是一个使用动态规划的字符串问题的解法，目标是判断字符串s是否能够被单词列表wordDict中的单词拼接而成。具体来说，使用一个布尔型数组dp记录s的前缀子串是否可以由wordDict中的单词拼接而成。数组dp的长度为s的长度+1，dp[0]被初始化为true，表示空字符串可以由空列表拼接而成。接下来，从i=1开始，对于每个i，将字符串s从0到i拆分成两个子串s[0:j]和s[j:i]，其中s[0:j]表示s的前缀子串，s[j:i]表示s的后缀子串。如果s[0:j]可以被拆分成由wordDict中的单词组成的子串，并且s[j:i]也在wordDict中，那么就可以将dp[i]设置为true。最后，返回dp[s.size()]表示整个字符串s是否可以被wordDict中的单词拼接而成。

1.动态规划

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size(), 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(wordSet.find(word) != wordSet.end() && dp[j]){
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};