LeetCode 139. 单词拆分

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

注意：

• 字典中的单词可以重复使用多次。
• 你可以假设字典中没有重复的单词。

示例：

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

解题过程循序渐进讲解

第一步：理解问题本质
题目核心是：给定字符串 s 和单词列表 wordDict，问能否用字典里的单词（可重复）完全拼出 s，不允许有多余字符，也不允许使用字典外的单词。这其实是一个 字符串分割 问题，分割出的每一段都必须在字典中。

例如 s = "leetcode"，若字典包含 "leet" 和 "code"，则可以分割成 "leet" + "code"。
若字典还包含 "le"、"et" 等，可能存在多种分割方式，但只要有一种能拼成全串即可。

第二步：初步思路——递归尝试（暴力搜索）
最直接的想法：从字符串开头开始，尝试所有可能的单词匹配。
设函数 canBreak(start) 表示：能否从位置 start 开始往后用字典拼出剩余部分。

• 从 start 位置向后扫描，每次截取子串 s[start:end]（end 从 start+1 到 n）。
• 如果这个子串在字典中，且剩余部分 canBreak(end) 也能拼出，则整体可以。
• 直到 end 到达末尾且子串在字典中，直接返回 true。

但这样会重复计算很多子问题。
例如：s = "aaaaa", wordDict = ["a","aa","aaa"]，递归树会指数爆炸。

第三步：引入记忆化搜索（自顶向下动态规划）
我们可以用数组 memo[i] 记录从位置 i 开始的子串能否被拼出。
memo[i] 取值：

• 0 表示未计算
• 1 表示可以
• -1 表示不可以

递归过程：

1. 如果 i == n（已到末尾），返回 true。
2. 如果 memo[i] 已计算过，直接返回。
3. 否则，枚举 end 从 i+1 到 n，截取 s[i:end]：
   • 如果在字典中，且递归判断 memo[end] 为真，则 memo[i] = true。
4. 如果所有 end 都不行，memo[i] = false。

这样避免了重复计算，时间复杂度为 O(n²)（每个 i 要枚举 end，且字典查询假设为 O(1)）。

第四步：转换为自底向上动态规划（更常见的解法）
定义 dp[i] 表示：字符串 s 的前 i 个字符（即 s[0:i]）能否被字典拼出。
注意：dp[0] 表示空串，默认为 true（空串总能被拼出）。

状态转移：

• 要计算 dp[i]，我们枚举 j 从 0 到 i-1，看 dp[j] 是否为 true。
• 如果 dp[j] 为 true，且子串 s[j:i] 在字典中，那么 dp[i] 就可以为 true。
• 即：前 j 个字符能拼出，且第 j 到 i-1 的字符组成的单词在字典中。

公式：
dp[i] = true 如果存在 j 使得 dp[j] == true 且 s[j:i] ∈ wordDict。
否则 dp[i] = false。

最终答案：dp[n]。

第五步：举例说明动态规划过程
以 s = "leetcode", wordDict = ["leet","code"] 为例：

• dp[0] = true（空串）。
• dp[1]：s[0:1]="l" 不在字典，false。
• dp[2]："le" 不在，false。
• dp[3]："lee" 不在，false。
• dp[4]：j=0, s[0:4]="leet" 在字典，且 dp[0]=true ⇒ dp[4]=true。
• dp[5]~dp[7]：类似，"e","t","c" 都不在字典，false。
• dp[8]：枚举 j：
  • j=4：dp[4]=true，且 s[4:8]="code" 在字典 ⇒ dp[8]=true。

结果 dp[8] 为 true。

第六步：优化字典查询与剪枝

• 将 wordDict 转为哈希集合 wordSet，使查询 O(1)。
• 枚举 j 时，可以只枚举 i - maxLen 到 i-1 的范围，其中 maxLen 是字典中最长单词的长度。因为如果 s[j:i] 长度大于 maxLen，肯定不在字典中。这可以剪枝。

第七步：最终算法步骤总结

1. 初始化 dp 数组长度为 n+1，dp[0]=true，其余为 false。
2. 获取字典中最长单词长度 maxLen。
3. 遍历 i 从 1 到 n：
   • 遍历 j 从 max(0, i-maxLen) 到 i-1：
     • 如果 dp[j]==true 且 s[j:i] 在 wordSet 中：
       • 设置 dp[i]=true，跳出内层循环。
4. 返回 dp[n]。

时间复杂度：O(n²) 或 O(n·maxLen)（剪枝后）。
空间复杂度：O(n) 用于 dp 数组。

第八步：代码框架（Python）

def wordBreak(s, wordDict):
    wordSet = set(wordDict)
    maxLen = max(len(w) for w in wordDict) if wordDict else 0
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    
    for i in range(1, n + 1):
        start = max(0, i - maxLen)
        for j in range(start, i):
            if dp[j] and s[j:i] in wordSet:
                dp[i] = True
                break
    return dp[n]

总结
该题是经典的 字符串分割+动态规划 问题，通过判断前缀子串的可拆分性，递推得到整个字符串的可拆分性。重点在于状态定义和转移方程的建立，以及利用字典最大长度进行剪枝优化。