LC139　单词拆分¶

中等通过率 60.6%python3核心代码模式动态规划样例通过牛客 AC字典树记忆化数组哈希表字符串动态规划Brute-Force Search

讲解章节：背包问题

一句话

f[i] 记「前 i 个字符能否拆完」，枚举最后一个词的长度往前接。

解题思路¶

这题考什么¶

直接搜索所有切法会指数爆炸："aaaa...a" 配上字典 ["a", "aa"] 时，每个字符缝都能切也能不切，方案数是 2 的 (n-1) 次方。但搜索里有大量重复子问题：无论前面怎么切，只要切到同一个位置 i，「剩下的 s[i:] 能否拆完」这个问题就完全一样。把它记下来就是动态规划，见线性 DP。

状态定义：f[i] 表示 s 的前 i 个字符 s[0:i] 能否被字典里的词完整拼出。转移方程（枚举最后一个词的长度 L）：

f[i] = 存在某个 L，使得 f[i-L] 为真且 s[i-L:i] 在字典里

初值 f[0] = True，表示空串平凡可拆。这一项不是形式上的补丁：它是整条递推唯一的真值来源，去掉它之后所有 f[i] 都会是 False。

为什么枚举「最后一个词」而不是「第一个词」：两种都对，但从后往前接可以直接复用已经算好的 f[i-L]，一趟正序循环即可，不需要递归。

枚举 L 时不必从 1 试到 i。字典里出现过的词长最多 20 种（题面限定词长 <= 20），把这些长度收集起来升序排好，只试这几种，同时用 L > i 提前收尾。

数据规模与复杂度¶

1 <= s.length <= 300，1 <= wordDict.length <= 1000， 1 <= wordDict[i].length <= 20，全为小写字母，字典内的词互不相同。时间 O(n * 不同词长数 * 词长)：300 * 20 次循环，每次做一个长度不超过 20 的子串切片与一次哈希查表，总量约 6000 次基本操作，是毫秒级。空间 O(n + 字典总字符数)。

把 wordDict 转成 set 是这份写法的性能前提。用原来的 list 做 in 判断，每次都要与至多 1000 个字符串逐个比较，300 * 20 * 1000 = 6e6 次字符串比较，比查表版慢三个数量级；set 的哈希查找是一次算哈希加一次比较。

坑在哪¶

f[0] = True 必须显式设。它代表「最后一个词恰好是整个前缀的开头」这种情形，漏掉之后 f[1..n] 全部为 False，任何输入都会返回 False。
f[i] 的下标 i 是长度不是位置，所以数组长度是 n + 1。写成 [False] * n 会在 f[n] 处越界。
s[i-L:i] 这个切片的含义是「以第 i 个字符结尾、长度为 L 的那一段」。切片的右端点是开区间，写成 s[i-L:i+1] 会多带一个字符，长度对不上。
长度升序加上 L > i 就 break，靠的是 lengths 已经排好序。若不排序而直接用 break，会在遇到第一个过长的词时提前退出，漏掉后面的短词；此时只能换成 continue，代价是每格都要走满全部长度。
词可以重复使用（题面明说），所以转移里没有任何「用过就划掉」的记号。若误加了使用标记，"applepenapple" 配 ["apple", "pen"] 就会返回 False。
只问能否拆分，不问方案数，所以内层找到一种就 break。继续枚举不会改变结果，只是白费功夫。

样例复核¶

s = "catsandog"，wordDict = ["cats","dog","sand","and","cat"]，词长集合为 {3, 4}。

f[3] = True（"cat"），f[4] = True（"cats"）
f[6]：L=3 时 f[3] 为真但 s[3:6] = "san" 不成词；L=4 时 f[2] 为假 -> False
f[7]：L=3 时 f[4] 为真且 s[4:7] = "and" 在字典里 -> True
f[5]：L=3 看 f[2]、L=4 看 f[1]，两者皆假 -> False
f[9]：L=3 时 f[6] 为假；L=4 时 f[5] 为假 -> False

两条路都不通，返回 False，与期望输出一致。前 7 个字符 "catsand" 拆得通（cats + and），末尾的 "og" 却成不了词—— 局部可拆推不出整体可拆，所以贪心地「见到词就切」在这题上不成立。

参考实现¶

solutions/leetcode/LC139/sol.py
from typing import List, Optional


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        # 转成 set 是性能前提：list 的 in 要与至多 1000 个字符串逐个比较，
        # set 是一次哈希查表。这一步不做，规模会从几千次膨胀到几百万次比较
        words = set(wordDict)
        # 只有字典里真实出现过的词长才值得枚举，最多 20 种。
        # 必须**升序**，下面的 break 才成立
        lengths = sorted({len(w) for w in words})
        # f[i] = 前 i 个字符能否拆完。下标 i 是长度不是位置，所以数组要 n+1 项。
        # f[0] = True 代表空串平凡可拆，它是整条递推唯一的真值来源，漏掉则全 False
        f = [False] * (n + 1)
        f[0] = True
        for i in range(1, n + 1):
            for L in lengths:
                if L > i:
                    break                    # 长度已升序，后面只会更长，本格到此为止
                # 假设最后一个词占 s[i-L:i]（右端开区间，正好 L 个字符），
                # 那么它前面的 i-L 个字符必须已经拆通
                if f[i - L] and s[i - L:i] in words:
                    f[i] = True
                    break                    # 只问能否，找到一种拆法就够，不必数方案
        return f[n]

LC139 单词拆分¶