139. 单词拆分

难度：🟡 Medium | 标签：动归、字符串 | 状态：⬜ LeetCode 链接

思路

dp[i] 表示 s[0..i) 能否被拆分。 转移：枚举切点 j，若 dp[j] && s[j..i) ∈ wordDict 则 dp[i] = true。

代码

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        int n = s.size();
        vector<char> dp(n + 1, false);
        dp[0] = true;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && dict.count(s.substr(j, i - j))) {
                    dp[i] = true; break;
                }
            }
        }
        return dp[n];
    }
};

复杂度

• 时间 O(n² · L)，L 平均单词长度
• 空间 O(n)

易错 / 回顾

• dp[0] = true（空串可拆）
• 优化：枚举 j 从 max(0, i - maxLen) 起，限制 substr 长度
• 140（输出所有拆分）：DFS + 记忆化