LeetCode 力扣热题100 单词拆分

题目解析

题目名称： 单词拆分（Word Break）

题目描述： 给定一个字符串 s 和一个字符串字典 wordDict，请判断 s 是否可以由 wordDict 中的单词拼接而成。一个单词可以在拆分时使用多次。

示例

string s = "leetcode";
vector<string> wordDict = {"leet", "code"};
Solution sol;
bool result = sol.wordBreak(s, wordDict); // 返回 true

解释：s 可以被拆分成 “leet” 和 “code”，它们都在 wordDict 中。

代码解析

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        // 1. 使用 unordered_set 存储 wordDict 以便 O(1) 查询单词
        unordered_set<string> wordDictSet(wordDict.begin(), wordDict.end());

        // 2. 定义动态规划数组 dp，其中 dp[i] 表示 s[0:i] 是否可以拆分
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true; // 空字符串可以拆分

        // 3. 动态规划填充 dp 数组
        for (int i = 1; i <= s.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                // 检查 s[j:i] 是否在 wordDictSet 中，并且前缀部分 s[0:j] 是否可拆分
                if (dp[j] && wordDictSet.find(s.substr(j, i - j)) != wordDictSet.end()) {
                    dp[i] = true;
                    break; // 只要找到一种可拆分方式就可以停止
                }
            }
        }

        // 4. 返回 s[0:s.size()] 是否可拆分
        return dp[s.size()];
    }
};

详细思路

1. 使用哈希表优化查询

我们将 wordDict 存入 unordered_set，这样可以在 O(1) 时间内查询单词是否存在，避免 O(n) 遍历字典。

2. 使用动态规划

定义 dp[i]，表示 s 的前 i 个字符 s[0:i] 是否可以被 wordDict 拆分。

• 状态转移方程 ：

即，如果 s[0:j] 可以被拆分 (dp[j] == true)，并且 s[j:i] 也在 wordDict 里，那么 dp[i] 也为 true。

• 初始条件 ：

• dp[0] = true，表示空字符串可以被拆分。

• 计算顺序 ：

• 我们按 i 从 1 到 s.size() 遍历，检查 s[j:i] 是否可拆分。

运行步骤示例

输入：

string s = "leetcode";
vector<string> wordDict = {"leet", "code"};

1. 初始化

• wordDictSet = {“leet”, “code”}

• dp = [true, false, false, false, false, false, false, false, false]

（dp[0] = true，其余初始化为 false）

2. 动态规划计算

遍历 i = 1 到 8：

i = 1

• j = 0 → s[0:1] = “l”，不在 wordDictSet，跳过。

i = 2

• j = 0, 1 → s[0:2] = “le”、s[1:2] = “e”，都不在 wordDictSet，跳过。

i = 3

• j = 0, 1, 2 → s[0:3] = “lee”、s[1:3] = “ee”、s[2:3] = “e”，都不在 wordDictSet，跳过。

i = 4

• j = 0 → s[0:4] = “leet”，在 wordDictSet，且 dp[0] = true，所以 dp[4] = true。

• dp 变为：

[true, false, false, false, true, false, false, false, false]

i = 5

• j = 0, 1, 2, 3, 4 → s[0:5] = “leetc”、s[1:5] = “eetc” 等都不在 wordDictSet，跳过。

i = 6

• j = 0, 1, 2, 3, 4, 5 → s[0:6] = “leetco” 等都不在 wordDictSet，跳过。

i = 7

• j = 0, 1, 2, 3, 4, 5, 6 → s[0:7] = “leetcod” 等都不在 wordDictSet，跳过。

i = 8

• j = 4 → s[4:8] = “code”，在 wordDictSet，且 dp[4] = true，所以 dp[8] = true。

• dp 变为：

[true, false, false, false, true, false, false, false, true]

3. 返回结果

最终 dp[8] = true，返回 true，表示 s 可以拆分。

时间复杂度分析

• 外层循环 ：遍历 s 长度 n，复杂度 O(n)。

• 内层循环 ：遍历 i 之前的所有 j，最坏情况下 O(n)。

• 哈希表查找 ：O(1)。

• 总复杂度 ：O(n^2)。

总结

定义 dp[i] ：表示 s[0:i] 是否可拆分。

状态转移方程 ：

• dp[i] = true 当 dp[j] == true 且 s[j:i] 在 wordDictSet 中。

时间复杂度 O(n^2) ，适用于 s 长度较短（一般小于 10^4）。

空间复杂度 O(n) ，主要是 dp 数组和 unordered_set。

这样，我们成功用 DP 解决了 单词拆分问题 ！ 🎯