好的，我们来看 LeetCode 第 139 题「单词拆分」。

题目描述

给定一个字符串 s 和一个字符串列表 wordDict 作为字典。请判断是否可以利用字典中出现的单词拼接出 s。

注意：

• 不要求字典中出现的单词全部都使用。
• 字典中的单词可以重复使用。

示例 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

解题思路

这个问题可以用 动态规划 来解决。

第一步：定义状态

我们定义 dp[i] 表示字符串 s 的前 i 个字符（即 s[0..i-1]）能否被字典中的单词拼接而成。

• 例如 dp[4] 表示 s[0..3] 这个子串能否被拆分。
• 最终目标是求 dp[n]，其中 n 是 s 的长度。

第二步：状态转移

为了计算 dp[i]，我们考虑前 i 个字符的最后一个单词可能是哪些：

• 我们枚举一个位置 j（0 <= j < i），将字符串分成两部分：
  • s[0..j-1] 对应 dp[j]：表示这部分能否被拆分。
  • s[j..i-1] 对应子串 substr(j, i-j)：检查它是否在字典中。
• 如果存在某个 j，使得 dp[j] 为 true，并且 s[j..i-1] 在字典中，那么 dp[i] 就为 true。

第三步：初始条件

dp[0] = true，表示空字符串可以被拆分（即不选任何单词即可组成空串）。

第四步：计算顺序

从小到大计算 dp[i]，i 从 1 到 n。

详细步骤示例

以 s = "leetcode", wordDict = ["leet", "code"] 为例：

1. 初始化：

   • dp[0] = true，其余为 false。

2. i = 1："l" 不在字典中，dp[1] = false。

3. i = 2："le" 不在字典中，dp[2] = false。

4. i = 3："lee" 不在字典中，dp[3] = false。

5. i = 4：

   • j = 0：dp[0] 为 true，检查 s[0..3] = "leet" 在字典中 → dp[4] = true。

6. i = 5～i = 7：没有单词匹配，保持 false。

7. i = 8：

   • j = 4：dp[4] 为 true，检查 s[4..7] = "code" 在字典中 → dp[8] = true。

最终 dp[8] 为 true，返回 true。

复杂度分析

• 时间复杂度：O(n²)，其中 n 是字符串长度。对每个 i，需要枚举 j 从 0 到 i-1。
• 空间复杂度：O(n) 用于 dp 数组，以及将 wordDict 转为哈希集合 O(m)（m 为字典中单词总长度）。

代码实现（思路）

def wordBreak(s, wordDict):
    word_set = set(wordDict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[n]

总结

这个问题的核心是：

• 将大问题分解为子问题：前 i 个字符能否拆分。
• 利用字典查找快速判断最后一个单词是否合法。
• 通过动态规划避免重复计算。

这样就能高效判断字符串是否能被字典单词拆分。