LeetCode86 - 单词拆分

📝 题目描述

题目链接：单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例：

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s 和 wordDict[i] 仅由小写英文字母组成
• wordDict 中的所有字符串 互不相同

💡 解题思路

方法一：自底向上的动态规划 - 标准写法

令 dp[i] 表示字符串前 i 个字符，也就是 s[0, i-1]，能否由字典中的单词拼接得到。

初始化 dp[0] = true 表示空字符串可以被成功拼接，这也是后续状态转移的起点。

进而我们可以得到状态转移方程：

$$dp[i] = dp[j]\ \&\&\ check(s[j...i - 1])$$

其中 $j$ 为分割点，$check(s[j..i−1])$ 表示子串 $s[j..i−1]$ 是否出现在字典中。

对于检查一个字符串是否出现在给定的字符串列表里一般可以考虑哈希表来快速判断，同时也可以做一些简单的剪枝，枚举分割点的时候倒着枚举，如果分割点 j 到 i 的长度已经大于字典列表里最长的单词的长度，那么就结束枚举，但是需要注意的是下面的代码给出的是不带剪枝的写法。

方法二：自底向上的动态规划 - 背包问题

这个题目其实可以直接套“零钱兑换”的模板。对于每一个 dp[i]：

• 遍历每一个字典的单词 t，检查 dp[i - t.length()] 是否有效；
• 有效，则检查子串 s[i - t..i] 是否正好等于单词 t。

也就是说，相当于“如果前缀有效，我拿字典里的每一个单词去试，看能不能拼在后面”。其实和“零钱兑换”的思路是类似的。

🔧 代码实现

1、自底向上的动态规划 - 标准写法

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        auto wordDictSet = unordered_set <string> ();
        // 将单词表加入集合
        for (auto word: wordDict) {
            wordDictSet.insert(word);
        }

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

        return dp[s.size()];
    }
};

2、自底向上的动态规划 - 背包问题

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int num = s.length();
        vector<bool> dp(num + 1, false);
        dp[0] = true;
        for (int i = 1; i <= num; i++) {
            for (const string& t : wordDict) {
                int tl = t.length();
                if ((i - tl >=0) && dp[i - tl] && (s.substr(i - tl, tl) == t)) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[num];
    }
};

📊 复杂度分析

1、自底向上的动态规划 - 标准写法

• 时间复杂度：$O(M \cdot L + N^3)$，将 wordDict 放入 unordered_set 中，需要遍历所有单词的所有字符，耗时 $O(M \cdot L)$；外层循环 i 执行 $N$ 次；内层循环 j 作为分割点，执行 $i$ 次（平均执行 $N / 2$ 次）；在最内层，截取子串的时间复杂度是 $O(i - j)$，最坏情况下接近 $O(N)$。
• 空间复杂度：$O(N + M \cdot L)$，dp 数组占用 $O(N)$，哈希集合占用 $O(M \cdot L)$ 。

2、自底向上的动态规划 - 背包问题

• 时间复杂度：$O(N \cdot M \cdot L)$，外层循环遍历字符串长度，执行 $N$ 次；内层循环遍历字典中的每一个单词，执行 $M$ 次；内层循环中，s.substr() 截取子串并进行字符串比较，这个操作的时间与单词长度有关，平均需要 $O(L)$ 的时间。
• 空间复杂度：$O(N)$，需要一个长度为 $N + 1$ 的 dp 数组来存储状态，占用 $O(N)$ 的空间。

🎯 总结

• 核心思想：记住动态规划的一般思路：找 dp 含义、初始状态、状态转移方程。