好的，我们这次来详细讲解 LeetCode 第 139 题「单词拆分」。
这道题是字符串与动态规划的经典结合题，我会从题意、思路推导、状态转移、边界情况、代码实现一步步带你理解。

1. 题目描述

题目链接：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

2. 题意理解与初步思路

我们要判断字符串 s 是否能被拆分成字典里的单词。
拆分必须完全覆盖 s，不能有多余字符，顺序也要一致。

关键点：

• 同一个单词可重复使用。
• 不要求所有拆分方案，只问是否可能。

初步想法：

• 如果从 s 的开头匹配到一个字典单词，那么剩下的部分就是一个子问题。
• 例如 s = "leetcode"，wordDict = ["leet","code"]：
  • 开头匹配 "leet" → 剩下 "code"。
  • 对 "code" 继续匹配，匹配到 "code" → 剩下空串，成功。
• 这提示我们可以用递归+记忆化或者动态规划。

3. 动态规划思路推导

我们定义：

• dp[i] 表示字符串 s 的前 i 个字符（即 s[0..i-1]）能否被拆分成字典中的单词。
• 最终目标是求 dp[n]，其中 n = len(s)。

状态转移：

• 如果前 j 个字符可以拆分（即 dp[j] == true），并且子串 s[j..i-1] 在字典中，那么 dp[i] = true。
• 即：dp[i] = true 当且仅当存在一个 j（0 ≤ j < i）使得 dp[j] == true 且 s[j:i] 在字典中。

初始条件：

• dp[0] = true 表示空串可以被拆分（这是合理的，因为空串不需要单词即可拆分）。

过程示例（示例 1）：

s = "leetcode", wordDict = ["leet", "code"]
n = 8

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

i=1..8 循环：
i=1: 检查 j=0: s[0:1]="l" 不在字典 → 不行。
i=2: j=0: "le" 不在；j=1: 但dp[1]是false → 不行。
i=3: 同理不行。
i=4: j=0: s[0:4]="leet" 在字典中 且 dp[0]=true → dp[4]=true。
i=5: 检查 j=0..4，没有满足的。
i=6,7 同理不行。
i=8: j=0: "leetcode" 不在字典；j=4: s[4:8]="code" 在字典 且 dp[4]=true → dp[8]=true。

结果 dp[8] = true。

4. 详细步骤拆解

步骤 1：定义 dp 数组

• 长度 n+1，布尔型，初始全 false，除了 dp[0]=true。

步骤 2：将 wordDict 转成集合（哈希表）

• 方便 O(1) 时间判断子串是否在字典。

步骤 3：递推填表

• 外层循环 i 从 1 到 n，表示考虑前 i 个字符。
• 内层循环 j 从 0 到 i-1：
  • 如果 dp[j] 为 true，并且子串 s[j:i] 在字典中，则设置 dp[i]=true 并跳出内层循环（因为只要一个 j 满足即可）。

步骤 4：返回结果

• dp[n]。

5. 复杂度分析

• 时间复杂度：O(n²)，因为两层循环，并且子串提取（s[j:i]）在 Python 中是 O(i-j)，但可优化（见后）。
• 空间复杂度：O(n) 用于 dp 数组，O(m) 用于字典集合（m 是字典中字符总数）。

6. 优化与细节

• 内层循环不必从 0 到 i-1 全部检查，可以限制 j 的范围：j 从 i - maxLen 到 i-1，其中 maxLen 是字典中最长单词的长度。因为如果 i-j > maxLen，子串肯定不在字典。
• 这样内层循环次数减少，优化到 O(n * maxLen)。

7. 代码实现（Python）

def wordBreak(s, wordDict):
    n = len(s)
    wordSet = set(wordDict)
    maxLen = max(len(word) for word in wordDict) if wordDict else 0
    
    dp = [False] * (n + 1)
    dp[0] = True  # 空串可拆分
    
    for i in range(1, n + 1):
        # j 从 i-1 往前找，但不超过最大单词长度范围
        start = max(0, i - maxLen) if maxLen > 0 else 0
        for j in range(start, i):
            if dp[j] and s[j:i] in wordSet:
                dp[i] = True
                break  # 找到一个可行的 j 即可
    return dp[n]

# 测试
print(wordBreak("leetcode", ["leet", "code"]))  # True
print(wordBreak("applepenapple", ["apple", "pen"]))  # True
print(wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"]))  # False

8. 总结

• 核心：将大问题分解为前缀子问题，利用 dp 数组记录子问题结果。
• 关键点：dp[i] 依赖于 dp[j] 和子串 s[j:i] 是否在字典。
• 优化：通过限制子串长度减少不必要的检查。

这样循序渐进地分析，你应该能清晰地理解「单词拆分」的解法思路了。