dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0 ... i - 1] 是否合法

每次把单词拆分成两部分，s = s1 + s2 (用 j 划分)，分别验证 s1 s2 是否合法

s1 → 使用 dp[j] 验证。

s2 → s[j..i - 1] 这个单词是否出现在 wordDict 中，使用哈希表

$$ ⁍ $$

对于每个 dp[i] 有不同的划分方式，就是遍历 j

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> set;
        for (const auto& word : wordDict) {
            set.insert(word);
        }

        int n = s.size();
        vector<bool> dp(n + 1);
        dp[0] = true;
        for (int i = 1; i <= n; i ++) {
            for (int j = 0; j < i; j ++) {
                if (dp[j] && set.find(s.substr(j, i - j)) != set.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

完全背包

需要注意遍历顺序，（需要统计所有次序，因此先遍历容量）

https://programmercarl.com/0139.单词拆分.html

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