139. 单词拆分这道题我在给新人讲动态规划时至少讲过二十遍每次都能看到同样的困惑字面意思那么简单为什么不能直接按顺序匹配它其实就是给你一个字符串 s 和一个单词列表 wordDict问能不能把 s 完全拆成若干个单词并且这些单词都出现在 wordDict 中。题目本身有很强的工程味文本解析、日志按已知词条切分、关键词识别背后都是同一套抽象模型。常见刷题网站把它编号为 139核心考点是动态规划但很多人卡住不是因为不会 DP而是没想清楚拆分为什么需要全局决策以及状态到底该怎么定义。这篇文章会从最直觉的贪心写法讲起用一个反例说明它为什么错然后给出暴力递归、记忆化搜索、一维 DP、两个关键优化最后聊几个面试官喜欢追问的进阶点。无论你是刚开始刷题还是想把这套思路迁移到实际业务里都可以直接对照使用。1. 题面拆解s 能被 wordDict 拼出来吗1.1 原题到底给了什么输入有很多刷题的人一眼扫过题目就以为懂了我建议慢一点先把输入约束看清楚。常见题面里s 的长度在 1 到 300 之间wordDict 最多 1000 个单词每个单词长度不超过 20。三个基本规则必须先记在脑子里wordDict 里的单词可以重复使用没有数量限制。这一点决定了问题本质是完全背包而非0-1 背包。拆分时每个单词都必须完整落在 s 中不能跳过字符也不能改变字符顺序。空字符串不会作为输入出现但在推导状态时可以作为基准条件。直接看示例更容易建立感觉swordDict结果leetcode[leet, code]trueapplepenapple[apple, pen]truecatsandog[cats, dog, sand, and, cat]false前两个例子都容易理解leetcode 切成 leet codeapplepenapple 切成 apple pen apple注意 apple 被重复使用了两次这正是单词可复用的含义。第三个例子值得多品一会catsandog 为什么是 false。你可能会想 cat sand dog但 cat 占了下标 0 到 2sand 占 3 到 6dog 需要从 7 开始而第 7 位是 o不是 d所以切不到 dog。cats and og 呢og 根本不在字典里。所有可能的切法都无法让最后一个单词落在字典中所以答案只能是 false。这个例子天然说明了不能只盯着字典里有没有某个词还要看它出现的位置是否和前面的切分衔接得上。1.2 把场景映射到真实需求单词拆分不是只在刷题时出现的抽象题。最常见的现实映射是分词给定一个词典判断一段文本能否由词典中的词拼接出来。比如你手里有一份公司内部术语表想判断某个描述是否全部由规范术语组成或者你有一组合法的 API 路径片段想校验一个 URL 是否完全由这些片段拼接而成。凡是用字典里的合法单元去覆盖整个序列的问题都可以抽象成这道题。另一个相关场景是敏感词替换或关键词屏蔽。你可以把允许出现的词看成一个白名单判断输入是否全部由白名单词汇组成。实际做的时候可能还要处理大小写、分隔符、同义词但核心判断逻辑和单词拆分一模一样所有字符都必须被某个合法单词完整覆盖不能漏字符也不能重叠。理解了这层映射你就可以把下面写的 DP 逻辑直接搬到自己项目里。2. 贪心匹配的第一个反例直接否定顺序切2.1 贪心思路与它的直觉来源拿到这道题大多数人的第一反应是从左往右扫描每到一个位置试着从当前位置往后找一个字典单词匹配上就把指针往后移动继续处理剩余部分。这种思路非常符合人类读句子的习惯。比如看到 leetcode先找 leet找到了再看 code也找到了于是得出结论能拆分。例子碰巧是对的于是人很容易误以为这就是正解。但你要知道人脑在读词的时候已经在潜意识里做了尝试多种切法再选合理的一种这件事。而贪心算法是机械地选第一个或最长的匹配选中之后就再也不回头了。一旦某个错误的早期决策堵住了后面的路贪心就永远翻不了身。2.2 一个 4 字符串就能让贪心翻车用一个很小的例子打破贪心s abcdwordDict [a, abc, b, cd]。如果贪心策略是每次取最长匹配前缀那么第一步会匹配到 abc因为它在字典里而且比 a 长。剩下的是 d但 d 不在字典里于是算法宣布失败。可正确答案是 true因为可以这样拆a b cd。这里的关键是第一次没有选最长可匹配前缀 abc而是选了更短的 a反而给后面的 b 和 cd 留下了空间。尝试顺序切分方式结果贪心取最长前缀abc dfalse最优a b cdtrue这个反例虽然小却把贪心的致命缺陷暴露得很彻底局部的最长匹配会给全局带来灾难而局部的短暂让步反而能解决整个问题。2.3 这个反例揭示了什么问题你可能会问那我把贪心策略改成每次取最短匹配前缀行不行不行。只要想一想 s abcdef字典里有 abcd、bcdef、a 这类组合短匹配也可能导致后续失败。更严重的是一旦字典里同时存在多个互为前缀的单词比如 a、ab、abc每一步都会面临多个可行选择而这些选择之间的冲突只有全局规划才能调和。因此这道题要求的不再是找一条匹配路径而是判断是否存在一条能从头走到尾的路径。这涉及对每个可能决策分支进行考量本质上是一个搜索问题或者递推问题。这也是为什么动态规划能成为标准解法的原因它把所有可行前缀路径的状态都记录下来最终只要看最后一个位置是否可达。3. 从暴力搜索到记忆化搜索3.1 用 DFS 枚举所有拆分点既然需要尝试多种切法最直接的做法就是递归定义 dfs(i) 表示 s 从下标 i 到结尾的子串能否被拆分。在函数内部从 i 后面枚举一个结束位置 end如果 s[i:end] 是字典里的单词并且 dfs(end) 也是 true那整个字符串就能拆。递归出口是 i 等于 n也就是已经处理到末尾说明前面所有部分都成功匹配了。写成代码就是这样from typing import List class Solution: def wordBreak(self, s: str, wordDict: List[str]) - bool: words set(wordDict) n len(s) def dfs(i: int) - bool: if i n: return True for end in range(i 1, n 1): if s[i:end] in words and dfs(end): return True return False return dfs(0)这段逻辑本身没有任何错误在小数据量下也能得出正确答案。但直接跑的话当 s 长度稍微大一点就会非常慢甚至超时。原因在于存在大量重复子问题。3.2 没有记忆化时会差到什么程度考虑 s aaaaaaaaaaaaaaaaaaaaaa字典里全是单字母 a、aa 这类词。dfs(0) 会尝试从每个位置切每切一次又会对更后面的位置再次调用 dfs。同一个 dfs(i) 可能被不同的前驱路径反复计算几百次。这种指数级的重复计算最坏情况会退化到接近 2 的 n 次方n300 时完全无法接受。你可能觉得把 end 从后往前遍历能让 dfs 先算出后面的答案从而省掉重复。这有一定的局部效果但并不能消除重复因为 dfs(i) 的答案只取决于 i 本身而它被调用的次数不受遍历顺序影响。真正的问题是同样的状态算了太多遍。3.3 记忆化的本质把子问题合并解决办法很朴素加一个缓存。Python 里最省事的是 lru_cachefrom functools import lru_cache from typing import List class Solution: def wordBreak(self, s: str, wordDict: List[str]) - bool: words set(wordDict) n len(s) lru_cache(None) def dfs(i: int) - bool: if i n: return True for end in range(i 1, n 1): if s[i:end] in words and dfs(end): return True return False return dfs(0)缓存之后dfs 的每个入参 i 只计算一次。状态总数是 O(n)每个状态内部枚举 end 最多 O(n) 次再加上每次判断 s[i:end] 是否在 words 中需要一次哈希查询整体复杂度在理想哈希下是 O(n^2)。原题 n 只有 300跑起来非常快已经可以 AC 了。记忆化搜索的本质是从上到下的动态规划递归的外壳递推的内核。它比纯 DP 写起来更贴近自然思维也更容易调试。我自己的经验是如果拿到一道递归题不知道该不该加记忆化先跑一个简单用例看是否存在大量重复调用如果存在直接加缓存往往就够了。3.4 递归版的适用边界记忆化搜索有两个隐患需要心里有数。一个是递归深度s 长度很大时可能触及系统栈上限。另一个是 Python 装饰器缓存会一直保留如果同一个函数在多次测试用例之间复用缓存可能带来脏数据。在刷题场景里 lru_cache 放在方法内部、每次调用自动重建问题不大但到了工程代码里如果递归函数是全局的就要小心缓存的清理策略。不过这道题的标准答案通常不是递归而是迭代式的一维 DP。原因倒不完全是因为递归性能差而是面试官更希望看到你能把递推关系用显式数组表达出来。接下来就进入主线。4. 一维 DP 的完整推导与两种写法4.1 状态定义为什么要用前 i 个字符动态规划的关键是状态定义。这里我们定义 dp[i] 表示 s 的前 i 个字符也就是 s[0:i]能否被拆分成字典中的单词组合。最终答案就是 dp[n]。为什么是前 i 个字符而不是从 i 开始的后缀因为空串天然可以作为初始状态dp[0] True 表示一个字符都没有的情况下我们已经处于拼接完成的状态。从头向后递推每一个新位置只需要回看已经计算好的更短前缀逻辑上很顺。转移方程可以这样描述dp[i] 为 true当且仅当存在某个 j满足 0 j i并且 dp[j] 是 true且 s[j:i] 是字典里的一个单词。这个方程看上去简单实际含义非常深刻它把整个问题拆成了两段前一段 s[0:j] 已经确认可拆后一段 s[j:i] 必须恰好是一个合法单词。j 是我们选择的切割点我们可以回看所有可能的 j只要有一个成立当前位置就可达。单词拆分也因此是典型的完全背包问题每个单词都可以反复使用但拼接顺序必须符合字符串顺序。4.2 dp[0] True 不是拍脑袋很多初学者不理解为什么 dp[0] 要设为 true。你可以这样想空字符串可以被视为0 个单词的合法拼接。如果 dp[0] 是 false那么第一个单词永远无法被拼接出来。比如 s[0:3] cat 在字典里我们需要 dp[0] s[0:3] in words 来得到 dp[3] true。没有这个基准第一次匹配就无从谈起。它和数学归纳法中证明 n0 成立是同一个动作少了它整个递推链条就断了。另外注意dp 数组长度是 n 1下标 i 直接对应 s 的前缀长度。这个设计能让状态和字符串切片保持一致dp[i] 对应 s[0:i]切片操作也是左闭右开写代码时不容易错位。4.3 写法一枚举分割点最直接的写法是外层遍历 i内层遍历所有可能的 jfrom typing import List class Solution: def wordBreak(self, s: str, wordDict: List[str]) - bool: words 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 words: dp[i] True break return dp[n]这里每到一个新位置 i就回头检查每一个可能的切割点 j。一旦找到一个合法切法就可以提前 break因为 dp[i] 已经是 true 了。这个版本在 n300 时表现很好逻辑也最贴近转移方程适合作为面试的第一版答案写出。4.4 写法二枚举字典中的单词第二种写法的思路反过来既然我们不知道哪个切割点最合适那就让字典中的每个单词 w 主动来匹配 dp 的当前位置。如果 dp[i-len(w)] 是 true并且 s[i-len(w):i] 正好等于 w那么 dp[i] 就是 true。from typing import List class Solution: def wordBreak(self, s: str, wordDict: List[str]) - bool: words set(wordDict) n len(s) dp [False] * (n 1) dp[0] True for i in range(1, n 1): for w in words: lw len(w) if i lw and dp[i - lw] and s[i - lw:i] w: dp[i] True break return dp[n]这个写法的理解要点是当前考虑的是以 i 结尾的一段这一段只能是某个字典单词 w所以它的起点必然是 i - len(w)。只要起点之前的前缀可拆这一段又恰好是 w那么当前位置就可达。两种写法在结果上等价但适用场景不完全一样。枚举分割点的版本性能受 s 的长度影响较大枚举单词的版本性能受字典大小和单词长度影响较大。如果字典很小枚举单词会更快如果字典很大但 s 很短枚举分割点反而更有优势。4.5 两种写法的复杂度如何比较不考虑字符串切片本身的拷贝成本枚举分割点的复杂度和经典的 O(n^2) 没有差别n 个位置每个位置平均回看 n/2 个 j。原题 n300这个量级完全够用。枚举单词版本的外层依然是 n 个位置内层最多 m 个单词每个单词做一次切片比较。最坏情况是 O(n * m * avg_len)当 m1000、avg_len20、n300 时大约是 6 万次比较量级也不差。真正要注意的是不要混淆枚举分割点版本里s[j:i] 的切片会随着 i 变长而变长枚举单词版本里每次比较的是固定长度的 w。所以第 5 节要讲的剪枝优化对两种写法都有明显收益。5. 两个性价比最高的优化5.1 wordDict 转 Set减少一整个量级如果你写过第一版代码就用 list 做s[j:i] in wordDict效率会非常难看。列表的 in 操作是线性扫描每个位置都要扫描整个字典n300、字典 1000 个词时总开销直接变成 9 万乘以 1000接近亿级别。把 wordDict 转成一个 set查询时间从 O(m) 降到哈希查询的 O(1)。这一步几乎是无脑的收益任何版本都应该先做。代码只需要一个words set(wordDict)但大多数人会忘记处理重复单词的问题。实际上如果字典里有重复单词set 会自动去重不会影响正确性反而让内层循环更快。5.2 用最长单词长度剪掉无效分割点原题给了单词长度不超过 20这个约束它可以直接用来剪枝。想一想当我们在枚举分割点 j 时如果 j 离 i 太远也就是 i - j 超过了字典里最长单词的长度那么 s[j:i] 绝对不可能出现在字典里这个 j 就是无效的。把内层循环从range(i)改成range(max(0, i - max_len), i)循环范围从 i 缩减到最多 max_len。当 max_len20n300 时每个位置最多只回看 20 个 j整个算法就变成 O(n * max_len) 量级和 O(n^2) 的差距非常明显。提示这个优化之所以安全是因为一个能匹配的单词长度不可能超过字典中最长单词的长度。只要把范围内的 j 全部检查一遍就不会漏掉任何合法切分。5.3 优化版完整代码把两个优化合进去枚举分割点的最终版代码长这样from typing import List class Solution: def wordBreak(self, s: str, wordDict: List[str]) - bool: words set(wordDict) max_len max(len(w) for w in wordDict) n len(s) dp [False] * (n 1) dp[0] True for i in range(1, n 1): start max(0, i - max_len) for j in range(start, i): if dp[j] and s[j:i] in words: dp[i] True break return dp[n]它依然保持可读性同时已经足够应对原题。很多人在拿这道题去面试时止步于此其实已经拿到一个不错的分数。如果你想继续拉开差距下一节的内容才是加分项。6. 面试官会顺着哪几条线深挖6.1 字典上万条时为什么可以考虑 Trie如果面试官追问字典非常大大到几千上万个单词怎么办说明他想看你对数据结构的迁移能力。Set 的查询虽然是 O(1)但内存占用随字典总字符数线性增长而且枚举分割点版本中即使有了 max_len 剪枝仍然会对每个长度做一次 set 查询其中不少查询其实是无效的。此时可以把字典建成一棵 Trie前缀树。从某个可达位置 i 出发不是去取一堆任意子串再查 set而是沿着 s[i:] 的字符一路检查 Trie 的路径每经过一个单词节点 end就说明 s[i:end] 是字典词这时如果 dp[i] 是 true就可以直接置 dp[end1] 为 true。Trie 版本的示意代码如下class TrieNode: def __init__(self): self.children {} self.is_end False class Solution: def wordBreak(self, s: str, wordDict: List[str]) - bool: root TrieNode() for w in wordDict: node root for ch in w: if ch not in node.children: node.children[ch] TrieNode() node node.children[ch] node.is_end True n len(s) dp [False] * (n 1) dp[0] True for i in range(n): if not dp[i]: continue node root for end in range(i, n): ch s[end] if ch not in node.children: break node node.children[ch] if node.is_end: dp[end 1] True return dp[n]这段代码的核心思想是从每个可达位置向外扩展不是回看前面能不能拆而是往前走把所有能从当前点延伸出去的合法单词终点标记为可达。Trie 会把当前前缀是否是某个字典词的前缀这个判断变得更加复用也避免了反复构造临时子串。Trie 版本的复杂度大约在 O(n * max_len) 或 O(n * 平均匹配深度)比朴素 Set 版本更可控。但不要因此过度设计如果字典只有几十个词Set 版本已经很快Trie 的构建代价反而可能成为负担。面试中先说 Set 版本再说可以用 Trie 优化是更稳妥的表达顺序。6.2 s 很长时内存与遍历的取舍如果面试官继续加压说 s 的长度可能到 10 的 5 次方甚至更大普通 DP 数组 O(n) 内存其实依然可接受真正的隐患是内层循环的回看范围。max_len 剪枝已经保证内层最多走 20 次那 O(n * max_len) 在 n10^5 时大概是 2 百万次完全能跑。这说明只要 max_len 不大这个方案对超长字符串依然能撑住。真正需要小心的反而是另一种情况max_len 很大比如某个字典词长度接近 n。这时即使剪枝也回退到 O(n^2)。如果面试官故意把字典里塞一个超长单词就需要考虑 Trie 版本因为它沿着 s 的字符逐步匹配一旦字符不匹配就立即停止不需要为每个位置检查所有可能长度。另外DP 数组其实只依赖当前点之前 max_len 个位置的状态所以可以用滑动窗口把内存进一步压到 O(max_len)。原题 n 很小这个优化收益不大但作为思路提出来能展示你对状态依赖关系的理解。6.3 从能否拆分到输出所有方案如果一个面试官前面聊得不错很可能会追加一句如果不仅要判断能不能拆还要输出所有拆分方案呢这对应更进阶的题目单词拆分 II。此时 bool 型 dp 不够用需要记录每个位置的前驱切法或者干脆改成 DFS 回溯。一种自然的方案是反向递归定义 dfs(i) 返回 s[i:] 的所有合法拆分方案列表。从 i 开始枚举每一个字典单词 w如果 s[i:len(w)] 恰好等于 w就把 w 拼接到 dfs(ilen(w)) 返回的所有方案前面。加上记忆化之后复杂度与合法方案总数相关。from functools import lru_cache class Solution: def wordBreak(self, s: str, wordDict: List[str]) - List[str]: words set(wordDict) n len(s) lru_cache(None) def dfs(i: int): if i n: return [[]] res [] for w in words: if s.startswith(w, i): for tail in dfs(i len(w)): res.append([w] tail) return res return [ .join(p) for p in dfs(0)]这个版本在方案非常多时有爆内存的风险。比如 s 全是 a字典是 a那么拆分方案可能只有一种但如果字典是 a、aa、……方案会组合爆炸。这种问题在真实业务里通常不是输出全部而是输出最优的一种或输出前 K 种所以还要加限制条件。6.4 业务中的变体最少段数、最长分词、动态词表把能否拆分升级到最少拆成几段几乎不用改架构把 dp 数组从 bool 改成 intdp[i] 记录前 i 个字符的最小段数初始化成无穷大只有合法切分才更新。同理最长分词就可以记录最大单词数或最长单段长度。动态词表的情况也值得注意。如果词表在系统运行时会更新每次全量重建 Set 或 Trie 会有开销。工程上的做法一般是维护一个版本号或使用可替换的数据结构词表更新时整体替换引用避免出现一半新词一半旧词的不一致状态。这些经验在刷题时不会体现但迁移到具体项目时非常实用。7. 写这道题时的真实踩坑记录7.1 dp 下标错位最常见的低级错误我见过很多人在初始化 dp 数组时写成dp [False] * n然后循环 i 从 0 到 n-1最后返回 dp[n-1]。他们想的是用下标对应当前字符位置但这样 dp[0] 就不再代表空串而是第一个字符。整个状态语义立刻乱掉转移方程也要跟着改bug 层出不穷。正确做法是写注释先固定语义# dp[i] 表示 s 的前 i 个字符是否可拆分dp[0] True dp [False] * (n 1) dp[0] True先想清楚 dp[i] 代表前 i 个字符再让循环 i 从 1 到 n所有切片用s[j:i]下标问题基本能避免。7.2 切片方向写反答案永远是 false枚举单词版本里最容易写错的判断条件是if i lw and dp[i - lw] and s[i - lw:i] w:新手容易误写成s[i:i lw] w。这个切出来的子串总是从当前位置往后和 dp[i-lw] 表示前一段可拆完全对不上。整个递推就变成前一段能拆但检查的是后一段语义被硬生生拆成两条线结果经常是 false。建议每次写完这种代码都拿一个具体例子手推一遍确认切片范围和 dp 下标对应同一个单词。还有一个类似的混淆如果把 dp 定义成后缀即 dp[i] 表示 s[i:] 是否能拆那么循环方向会反过来初始化 dp[n]True判断条件是s[i:ilen(w)] w且 dp[ilen(w)] 为 true。两种定义都可以但不要混着写混写的代码跑起来就像在跳探戈自己都看不懂。7.3 不是所有场景都需要上 Trie这道题的讨论热度高网上的题解也各种各样导致一些人一上来就写 Trie代码长了容易错面试时一旦讲不清反而减分。我的建议是先稳稳写出 Set 一维 DP 的版本再用 max_len 剪枝把复杂度压下去最后根据面试官的反应决定要不要讲 Trie 优化。大部分面试场景下能被引导着讲清楚 Trie 的动机已经比背一整套 Trie 代码更有价值。7.4 面试表达上的一个建议讲解这道题时一定要先讲贪心为什么不行。讲反例的过程其实是让面试官看懂你是在解决问题而不是背模板。很多人上来就写 dp看起来代码对但面试官一问 dp[0] 为什么是 true就答不上来。能解释清楚状态定义和转移方程比写出最优解更能拉高印象分。我个人很喜欢用这道题作为从贪心到搜索再到动态规划的完整过渡案例先否定贪心再用暴力递归验证想法加缓存后意识到递推关系最后抽象成一维 DP。这个过程是很多动态规划题目的通用思考路径熟练掌握之后遇到分割回文串戳气球买卖股票这类题你也能用同样的思路快速定位状态和转移。最后分享一个写码习惯先把 dp 数组和 dp[0] 的注释写在前面再写循环再写转移条件最后跑示例。这个顺序能避免绝大多数下标和方向错误。这道题本身不难但它很适合用来检验你对状态是怎么来的理解是否深入而不仅仅是答案能不能跑通。
139. 单词拆分这道题我在给新人讲动态规划时至少讲过二十遍每次都能看到同样的困惑字面意思那么简单为什么不能直接按顺序匹配它其实就是给你一个字符串 s 和一个单词列表 wordDict问能不能把 s 完全拆成若干个单词并且这些单词都出现在 wordDict 中。题目本身有很强的工程味文本解析、日志按已知词条切分、关键词识别背后都是同一套抽象模型。常见刷题网站把它编号为 139核心考点是动态规划但很多人卡住不是因为不会 DP而是没想清楚拆分为什么需要全局决策以及状态到底该怎么定义。这篇文章会从最直觉的贪心写法讲起用一个反例说明它为什么错然后给出暴力递归、记忆化搜索、一维 DP、两个关键优化最后聊几个面试官喜欢追问的进阶点。无论你是刚开始刷题还是想把这套思路迁移到实际业务里都可以直接对照使用。1. 题面拆解s 能被 wordDict 拼出来吗1.1 原题到底给了什么输入有很多刷题的人一眼扫过题目就以为懂了我建议慢一点先把输入约束看清楚。常见题面里s 的长度在 1 到 300 之间wordDict 最多 1000 个单词每个单词长度不超过 20。三个基本规则必须先记在脑子里wordDict 里的单词可以重复使用没有数量限制。这一点决定了问题本质是完全背包而非0-1 背包。拆分时每个单词都必须完整落在 s 中不能跳过字符也不能改变字符顺序。空字符串不会作为输入出现但在推导状态时可以作为基准条件。直接看示例更容易建立感觉swordDict结果leetcode[leet, code]trueapplepenapple[apple, pen]truecatsandog[cats, dog, sand, and, cat]false前两个例子都容易理解leetcode 切成 leet codeapplepenapple 切成 apple pen apple注意 apple 被重复使用了两次这正是单词可复用的含义。第三个例子值得多品一会catsandog 为什么是 false。你可能会想 cat sand dog但 cat 占了下标 0 到 2sand 占 3 到 6dog 需要从 7 开始而第 7 位是 o不是 d所以切不到 dog。cats and og 呢og 根本不在字典里。所有可能的切法都无法让最后一个单词落在字典中所以答案只能是 false。这个例子天然说明了不能只盯着字典里有没有某个词还要看它出现的位置是否和前面的切分衔接得上。1.2 把场景映射到真实需求单词拆分不是只在刷题时出现的抽象题。最常见的现实映射是分词给定一个词典判断一段文本能否由词典中的词拼接出来。比如你手里有一份公司内部术语表想判断某个描述是否全部由规范术语组成或者你有一组合法的 API 路径片段想校验一个 URL 是否完全由这些片段拼接而成。凡是用字典里的合法单元去覆盖整个序列的问题都可以抽象成这道题。另一个相关场景是敏感词替换或关键词屏蔽。你可以把允许出现的词看成一个白名单判断输入是否全部由白名单词汇组成。实际做的时候可能还要处理大小写、分隔符、同义词但核心判断逻辑和单词拆分一模一样所有字符都必须被某个合法单词完整覆盖不能漏字符也不能重叠。理解了这层映射你就可以把下面写的 DP 逻辑直接搬到自己项目里。2. 贪心匹配的第一个反例直接否定顺序切2.1 贪心思路与它的直觉来源拿到这道题大多数人的第一反应是从左往右扫描每到一个位置试着从当前位置往后找一个字典单词匹配上就把指针往后移动继续处理剩余部分。这种思路非常符合人类读句子的习惯。比如看到 leetcode先找 leet找到了再看 code也找到了于是得出结论能拆分。例子碰巧是对的于是人很容易误以为这就是正解。但你要知道人脑在读词的时候已经在潜意识里做了尝试多种切法再选合理的一种这件事。而贪心算法是机械地选第一个或最长的匹配选中之后就再也不回头了。一旦某个错误的早期决策堵住了后面的路贪心就永远翻不了身。2.2 一个 4 字符串就能让贪心翻车用一个很小的例子打破贪心s abcdwordDict [a, abc, b, cd]。如果贪心策略是每次取最长匹配前缀那么第一步会匹配到 abc因为它在字典里而且比 a 长。剩下的是 d但 d 不在字典里于是算法宣布失败。可正确答案是 true因为可以这样拆a b cd。这里的关键是第一次没有选最长可匹配前缀 abc而是选了更短的 a反而给后面的 b 和 cd 留下了空间。尝试顺序切分方式结果贪心取最长前缀abc dfalse最优a b cdtrue这个反例虽然小却把贪心的致命缺陷暴露得很彻底局部的最长匹配会给全局带来灾难而局部的短暂让步反而能解决整个问题。2.3 这个反例揭示了什么问题你可能会问那我把贪心策略改成每次取最短匹配前缀行不行不行。只要想一想 s abcdef字典里有 abcd、bcdef、a 这类组合短匹配也可能导致后续失败。更严重的是一旦字典里同时存在多个互为前缀的单词比如 a、ab、abc每一步都会面临多个可行选择而这些选择之间的冲突只有全局规划才能调和。因此这道题要求的不再是找一条匹配路径而是判断是否存在一条能从头走到尾的路径。这涉及对每个可能决策分支进行考量本质上是一个搜索问题或者递推问题。这也是为什么动态规划能成为标准解法的原因它把所有可行前缀路径的状态都记录下来最终只要看最后一个位置是否可达。3. 从暴力搜索到记忆化搜索3.1 用 DFS 枚举所有拆分点既然需要尝试多种切法最直接的做法就是递归定义 dfs(i) 表示 s 从下标 i 到结尾的子串能否被拆分。在函数内部从 i 后面枚举一个结束位置 end如果 s[i:end] 是字典里的单词并且 dfs(end) 也是 true那整个字符串就能拆。递归出口是 i 等于 n也就是已经处理到末尾说明前面所有部分都成功匹配了。写成代码就是这样from typing import List class Solution: def wordBreak(self, s: str, wordDict: List[str]) - bool: words set(wordDict) n len(s) def dfs(i: int) - bool: if i n: return True for end in range(i 1, n 1): if s[i:end] in words and dfs(end): return True return False return dfs(0)这段逻辑本身没有任何错误在小数据量下也能得出正确答案。但直接跑的话当 s 长度稍微大一点就会非常慢甚至超时。原因在于存在大量重复子问题。3.2 没有记忆化时会差到什么程度考虑 s aaaaaaaaaaaaaaaaaaaaaa字典里全是单字母 a、aa 这类词。dfs(0) 会尝试从每个位置切每切一次又会对更后面的位置再次调用 dfs。同一个 dfs(i) 可能被不同的前驱路径反复计算几百次。这种指数级的重复计算最坏情况会退化到接近 2 的 n 次方n300 时完全无法接受。你可能觉得把 end 从后往前遍历能让 dfs 先算出后面的答案从而省掉重复。这有一定的局部效果但并不能消除重复因为 dfs(i) 的答案只取决于 i 本身而它被调用的次数不受遍历顺序影响。真正的问题是同样的状态算了太多遍。3.3 记忆化的本质把子问题合并解决办法很朴素加一个缓存。Python 里最省事的是 lru_cachefrom functools import lru_cache from typing import List class Solution: def wordBreak(self, s: str, wordDict: List[str]) - bool: words set(wordDict) n len(s) lru_cache(None) def dfs(i: int) - bool: if i n: return True for end in range(i 1, n 1): if s[i:end] in words and dfs(end): return True return False return dfs(0)缓存之后dfs 的每个入参 i 只计算一次。状态总数是 O(n)每个状态内部枚举 end 最多 O(n) 次再加上每次判断 s[i:end] 是否在 words 中需要一次哈希查询整体复杂度在理想哈希下是 O(n^2)。原题 n 只有 300跑起来非常快已经可以 AC 了。记忆化搜索的本质是从上到下的动态规划递归的外壳递推的内核。它比纯 DP 写起来更贴近自然思维也更容易调试。我自己的经验是如果拿到一道递归题不知道该不该加记忆化先跑一个简单用例看是否存在大量重复调用如果存在直接加缓存往往就够了。3.4 递归版的适用边界记忆化搜索有两个隐患需要心里有数。一个是递归深度s 长度很大时可能触及系统栈上限。另一个是 Python 装饰器缓存会一直保留如果同一个函数在多次测试用例之间复用缓存可能带来脏数据。在刷题场景里 lru_cache 放在方法内部、每次调用自动重建问题不大但到了工程代码里如果递归函数是全局的就要小心缓存的清理策略。不过这道题的标准答案通常不是递归而是迭代式的一维 DP。原因倒不完全是因为递归性能差而是面试官更希望看到你能把递推关系用显式数组表达出来。接下来就进入主线。4. 一维 DP 的完整推导与两种写法4.1 状态定义为什么要用前 i 个字符动态规划的关键是状态定义。这里我们定义 dp[i] 表示 s 的前 i 个字符也就是 s[0:i]能否被拆分成字典中的单词组合。最终答案就是 dp[n]。为什么是前 i 个字符而不是从 i 开始的后缀因为空串天然可以作为初始状态dp[0] True 表示一个字符都没有的情况下我们已经处于拼接完成的状态。从头向后递推每一个新位置只需要回看已经计算好的更短前缀逻辑上很顺。转移方程可以这样描述dp[i] 为 true当且仅当存在某个 j满足 0 j i并且 dp[j] 是 true且 s[j:i] 是字典里的一个单词。这个方程看上去简单实际含义非常深刻它把整个问题拆成了两段前一段 s[0:j] 已经确认可拆后一段 s[j:i] 必须恰好是一个合法单词。j 是我们选择的切割点我们可以回看所有可能的 j只要有一个成立当前位置就可达。单词拆分也因此是典型的完全背包问题每个单词都可以反复使用但拼接顺序必须符合字符串顺序。4.2 dp[0] True 不是拍脑袋很多初学者不理解为什么 dp[0] 要设为 true。你可以这样想空字符串可以被视为0 个单词的合法拼接。如果 dp[0] 是 false那么第一个单词永远无法被拼接出来。比如 s[0:3] cat 在字典里我们需要 dp[0] s[0:3] in words 来得到 dp[3] true。没有这个基准第一次匹配就无从谈起。它和数学归纳法中证明 n0 成立是同一个动作少了它整个递推链条就断了。另外注意dp 数组长度是 n 1下标 i 直接对应 s 的前缀长度。这个设计能让状态和字符串切片保持一致dp[i] 对应 s[0:i]切片操作也是左闭右开写代码时不容易错位。4.3 写法一枚举分割点最直接的写法是外层遍历 i内层遍历所有可能的 jfrom typing import List class Solution: def wordBreak(self, s: str, wordDict: List[str]) - bool: words 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 words: dp[i] True break return dp[n]这里每到一个新位置 i就回头检查每一个可能的切割点 j。一旦找到一个合法切法就可以提前 break因为 dp[i] 已经是 true 了。这个版本在 n300 时表现很好逻辑也最贴近转移方程适合作为面试的第一版答案写出。4.4 写法二枚举字典中的单词第二种写法的思路反过来既然我们不知道哪个切割点最合适那就让字典中的每个单词 w 主动来匹配 dp 的当前位置。如果 dp[i-len(w)] 是 true并且 s[i-len(w):i] 正好等于 w那么 dp[i] 就是 true。from typing import List class Solution: def wordBreak(self, s: str, wordDict: List[str]) - bool: words set(wordDict) n len(s) dp [False] * (n 1) dp[0] True for i in range(1, n 1): for w in words: lw len(w) if i lw and dp[i - lw] and s[i - lw:i] w: dp[i] True break return dp[n]这个写法的理解要点是当前考虑的是以 i 结尾的一段这一段只能是某个字典单词 w所以它的起点必然是 i - len(w)。只要起点之前的前缀可拆这一段又恰好是 w那么当前位置就可达。两种写法在结果上等价但适用场景不完全一样。枚举分割点的版本性能受 s 的长度影响较大枚举单词的版本性能受字典大小和单词长度影响较大。如果字典很小枚举单词会更快如果字典很大但 s 很短枚举分割点反而更有优势。4.5 两种写法的复杂度如何比较不考虑字符串切片本身的拷贝成本枚举分割点的复杂度和经典的 O(n^2) 没有差别n 个位置每个位置平均回看 n/2 个 j。原题 n300这个量级完全够用。枚举单词版本的外层依然是 n 个位置内层最多 m 个单词每个单词做一次切片比较。最坏情况是 O(n * m * avg_len)当 m1000、avg_len20、n300 时大约是 6 万次比较量级也不差。真正要注意的是不要混淆枚举分割点版本里s[j:i] 的切片会随着 i 变长而变长枚举单词版本里每次比较的是固定长度的 w。所以第 5 节要讲的剪枝优化对两种写法都有明显收益。5. 两个性价比最高的优化5.1 wordDict 转 Set减少一整个量级如果你写过第一版代码就用 list 做s[j:i] in wordDict效率会非常难看。列表的 in 操作是线性扫描每个位置都要扫描整个字典n300、字典 1000 个词时总开销直接变成 9 万乘以 1000接近亿级别。把 wordDict 转成一个 set查询时间从 O(m) 降到哈希查询的 O(1)。这一步几乎是无脑的收益任何版本都应该先做。代码只需要一个words set(wordDict)但大多数人会忘记处理重复单词的问题。实际上如果字典里有重复单词set 会自动去重不会影响正确性反而让内层循环更快。5.2 用最长单词长度剪掉无效分割点原题给了单词长度不超过 20这个约束它可以直接用来剪枝。想一想当我们在枚举分割点 j 时如果 j 离 i 太远也就是 i - j 超过了字典里最长单词的长度那么 s[j:i] 绝对不可能出现在字典里这个 j 就是无效的。把内层循环从range(i)改成range(max(0, i - max_len), i)循环范围从 i 缩减到最多 max_len。当 max_len20n300 时每个位置最多只回看 20 个 j整个算法就变成 O(n * max_len) 量级和 O(n^2) 的差距非常明显。提示这个优化之所以安全是因为一个能匹配的单词长度不可能超过字典中最长单词的长度。只要把范围内的 j 全部检查一遍就不会漏掉任何合法切分。5.3 优化版完整代码把两个优化合进去枚举分割点的最终版代码长这样from typing import List class Solution: def wordBreak(self, s: str, wordDict: List[str]) - bool: words set(wordDict) max_len max(len(w) for w in wordDict) n len(s) dp [False] * (n 1) dp[0] True for i in range(1, n 1): start max(0, i - max_len) for j in range(start, i): if dp[j] and s[j:i] in words: dp[i] True break return dp[n]它依然保持可读性同时已经足够应对原题。很多人在拿这道题去面试时止步于此其实已经拿到一个不错的分数。如果你想继续拉开差距下一节的内容才是加分项。6. 面试官会顺着哪几条线深挖6.1 字典上万条时为什么可以考虑 Trie如果面试官追问字典非常大大到几千上万个单词怎么办说明他想看你对数据结构的迁移能力。Set 的查询虽然是 O(1)但内存占用随字典总字符数线性增长而且枚举分割点版本中即使有了 max_len 剪枝仍然会对每个长度做一次 set 查询其中不少查询其实是无效的。此时可以把字典建成一棵 Trie前缀树。从某个可达位置 i 出发不是去取一堆任意子串再查 set而是沿着 s[i:] 的字符一路检查 Trie 的路径每经过一个单词节点 end就说明 s[i:end] 是字典词这时如果 dp[i] 是 true就可以直接置 dp[end1] 为 true。Trie 版本的示意代码如下class TrieNode: def __init__(self): self.children {} self.is_end False class Solution: def wordBreak(self, s: str, wordDict: List[str]) - bool: root TrieNode() for w in wordDict: node root for ch in w: if ch not in node.children: node.children[ch] TrieNode() node node.children[ch] node.is_end True n len(s) dp [False] * (n 1) dp[0] True for i in range(n): if not dp[i]: continue node root for end in range(i, n): ch s[end] if ch not in node.children: break node node.children[ch] if node.is_end: dp[end 1] True return dp[n]这段代码的核心思想是从每个可达位置向外扩展不是回看前面能不能拆而是往前走把所有能从当前点延伸出去的合法单词终点标记为可达。Trie 会把当前前缀是否是某个字典词的前缀这个判断变得更加复用也避免了反复构造临时子串。Trie 版本的复杂度大约在 O(n * max_len) 或 O(n * 平均匹配深度)比朴素 Set 版本更可控。但不要因此过度设计如果字典只有几十个词Set 版本已经很快Trie 的构建代价反而可能成为负担。面试中先说 Set 版本再说可以用 Trie 优化是更稳妥的表达顺序。6.2 s 很长时内存与遍历的取舍如果面试官继续加压说 s 的长度可能到 10 的 5 次方甚至更大普通 DP 数组 O(n) 内存其实依然可接受真正的隐患是内层循环的回看范围。max_len 剪枝已经保证内层最多走 20 次那 O(n * max_len) 在 n10^5 时大概是 2 百万次完全能跑。这说明只要 max_len 不大这个方案对超长字符串依然能撑住。真正需要小心的反而是另一种情况max_len 很大比如某个字典词长度接近 n。这时即使剪枝也回退到 O(n^2)。如果面试官故意把字典里塞一个超长单词就需要考虑 Trie 版本因为它沿着 s 的字符逐步匹配一旦字符不匹配就立即停止不需要为每个位置检查所有可能长度。另外DP 数组其实只依赖当前点之前 max_len 个位置的状态所以可以用滑动窗口把内存进一步压到 O(max_len)。原题 n 很小这个优化收益不大但作为思路提出来能展示你对状态依赖关系的理解。6.3 从能否拆分到输出所有方案如果一个面试官前面聊得不错很可能会追加一句如果不仅要判断能不能拆还要输出所有拆分方案呢这对应更进阶的题目单词拆分 II。此时 bool 型 dp 不够用需要记录每个位置的前驱切法或者干脆改成 DFS 回溯。一种自然的方案是反向递归定义 dfs(i) 返回 s[i:] 的所有合法拆分方案列表。从 i 开始枚举每一个字典单词 w如果 s[i:len(w)] 恰好等于 w就把 w 拼接到 dfs(ilen(w)) 返回的所有方案前面。加上记忆化之后复杂度与合法方案总数相关。from functools import lru_cache class Solution: def wordBreak(self, s: str, wordDict: List[str]) - List[str]: words set(wordDict) n len(s) lru_cache(None) def dfs(i: int): if i n: return [[]] res [] for w in words: if s.startswith(w, i): for tail in dfs(i len(w)): res.append([w] tail) return res return [ .join(p) for p in dfs(0)]这个版本在方案非常多时有爆内存的风险。比如 s 全是 a字典是 a那么拆分方案可能只有一种但如果字典是 a、aa、……方案会组合爆炸。这种问题在真实业务里通常不是输出全部而是输出最优的一种或输出前 K 种所以还要加限制条件。6.4 业务中的变体最少段数、最长分词、动态词表把能否拆分升级到最少拆成几段几乎不用改架构把 dp 数组从 bool 改成 intdp[i] 记录前 i 个字符的最小段数初始化成无穷大只有合法切分才更新。同理最长分词就可以记录最大单词数或最长单段长度。动态词表的情况也值得注意。如果词表在系统运行时会更新每次全量重建 Set 或 Trie 会有开销。工程上的做法一般是维护一个版本号或使用可替换的数据结构词表更新时整体替换引用避免出现一半新词一半旧词的不一致状态。这些经验在刷题时不会体现但迁移到具体项目时非常实用。7. 写这道题时的真实踩坑记录7.1 dp 下标错位最常见的低级错误我见过很多人在初始化 dp 数组时写成dp [False] * n然后循环 i 从 0 到 n-1最后返回 dp[n-1]。他们想的是用下标对应当前字符位置但这样 dp[0] 就不再代表空串而是第一个字符。整个状态语义立刻乱掉转移方程也要跟着改bug 层出不穷。正确做法是写注释先固定语义# dp[i] 表示 s 的前 i 个字符是否可拆分dp[0] True dp [False] * (n 1) dp[0] True先想清楚 dp[i] 代表前 i 个字符再让循环 i 从 1 到 n所有切片用s[j:i]下标问题基本能避免。7.2 切片方向写反答案永远是 false枚举单词版本里最容易写错的判断条件是if i lw and dp[i - lw] and s[i - lw:i] w:新手容易误写成s[i:i lw] w。这个切出来的子串总是从当前位置往后和 dp[i-lw] 表示前一段可拆完全对不上。整个递推就变成前一段能拆但检查的是后一段语义被硬生生拆成两条线结果经常是 false。建议每次写完这种代码都拿一个具体例子手推一遍确认切片范围和 dp 下标对应同一个单词。还有一个类似的混淆如果把 dp 定义成后缀即 dp[i] 表示 s[i:] 是否能拆那么循环方向会反过来初始化 dp[n]True判断条件是s[i:ilen(w)] w且 dp[ilen(w)] 为 true。两种定义都可以但不要混着写混写的代码跑起来就像在跳探戈自己都看不懂。7.3 不是所有场景都需要上 Trie这道题的讨论热度高网上的题解也各种各样导致一些人一上来就写 Trie代码长了容易错面试时一旦讲不清反而减分。我的建议是先稳稳写出 Set 一维 DP 的版本再用 max_len 剪枝把复杂度压下去最后根据面试官的反应决定要不要讲 Trie 优化。大部分面试场景下能被引导着讲清楚 Trie 的动机已经比背一整套 Trie 代码更有价值。7.4 面试表达上的一个建议讲解这道题时一定要先讲贪心为什么不行。讲反例的过程其实是让面试官看懂你是在解决问题而不是背模板。很多人上来就写 dp看起来代码对但面试官一问 dp[0] 为什么是 true就答不上来。能解释清楚状态定义和转移方程比写出最优解更能拉高印象分。我个人很喜欢用这道题作为从贪心到搜索再到动态规划的完整过渡案例先否定贪心再用暴力递归验证想法加缓存后意识到递推关系最后抽象成一维 DP。这个过程是很多动态规划题目的通用思考路径熟练掌握之后遇到分割回文串戳气球买卖股票这类题你也能用同样的思路快速定位状态和转移。最后分享一个写码习惯先把 dp 数组和 dp[0] 的注释写在前面再写循环再写转移条件最后跑示例。这个顺序能避免绝大多数下标和方向错误。这道题本身不难但它很适合用来检验你对状态是怎么来的理解是否深入而不仅仅是答案能不能跑通。
