企业官网建设流程全解析

刷题刷到一定量之后会发现，动态规划类的题目其实就那么几类套路，而“单词拆分”这道题恰恰是把套路讲明白的绝佳样本。我第一次见到 LeetCode 139 的时候，第一反应是想用双指针或者贪心去扫，结果被一个经典反例直接打脸，后来才老老实实去理解动态规划的状态定义。

这题在 LeetCode 上是 Medium 难度，但实际上它的核心思想并不难，难的是很多人看完题解会写代码，却说不清楚为什么 dp 数组要这样定义、为什么遍历顺序要这样设计。这篇文章不打算只贴代码，我想把从暴力递归、到记忆化搜索、再到正经动态规划、再到 BFS 视角的完整推导过程都捋一遍，顺带把实际刷题和面试里容易踩的坑一并讲清楚。不管你是刚开始刷 DP 的小白，还是准备面试想快速过一遍经典题的进阶选手，这篇应该都能给你点东西。

1. 先搞清楚这道题到底在问什么

1.1 题面本质：不是“查单词”，是“判断可拆分性”

题目描述很简单：给定一个非空字符串 s，和一个包含非空单词的列表 wordDict，判断 s 是否可以被空格拆分成一个或多个字典中出现的单词。

比如 s = "leetcode"，wordDict = ["leet", "code"]，那结果就是 True，因为可以拆成 "leet" + "code"。

但要注意，这题的问题描述里藏着两个关键点，很多人会忽略：

第一，它问的是“能不能拆”，不是“有几种拆法”，也不是“拆出的结果是什么”。这意味着我们只需要一个布尔值来标记可达状态，不需要记录完整的拆分路径。如果你一上来就想用回溯把所有拆分可能列出来，那就把简单问题做复杂了。

第二，字典中的单词可以重复使用，而且每个单词的使用次数不限。这其实是在暗示一个问题：这题的可拆分性是可以“传递”的。如果字符串的一个前缀可以被拆成合法单词，那么从它延伸出去的另一个前缀能否被拆分，就只取决于多出来的那段子串是不是字典里的单词。这样的问题结构天然适合动态规划，因为它具备“子问题重叠”和“最优子结构”两个特征。

1.2 三种想当然的错误思路

这道题之所以容易做错，是因为它长着一张“可以用简单方法搞定”的脸。我见过不少人在刷题群里分享自己的骚操作，总结下来大体有三种，最后都被测试用例击穿了。

第一种是正向贪心。从 s 的开头开始，能匹配到字典里最长的词就切一刀，然后继续切剩下的部分。这种思路的翻车案例非常经典：s = "catsandog"，wordDict = ["cats", "dog", "sand", "and", "cat"]。如果用贪心，先匹配最长词，会切出 "cats" + "and" + "og"，"og" 不在字典里，最后判定不可拆分。但实际上 "cat" + "sand" + "og" 也不行，因为 "og" 依然不在。真正的问题在于，“catsandog” 无论怎么拆都无法由这五个词拼出来，而贪心算法从一开始选择了 "cats"，就直接绕到了死胡同里，哪怕后面存在一种合法拆分，只要第一步选错了，整体就错了。

第二种是反向贪心，从尾部往前匹配。看着好像能解决一部分问题，但只要构造一个“长词包含短词”的用例，反向贪心同样会翻车，本质和正向贪心是一样的。

第三种是用正则或者字符串替换，把字典里的词不断从 s 中删除。这种方法的问题更隐蔽：删除顺序不同会导致结果不同。比如 s = "abcde"，wordDict = ["abc", "bcde"]，如果先删 "abc"，剩下 "de" 无法继续删，返回 False；如果先删 "bcde"，剩下 "a" 也无法继续删，还是 False。但换个用例，s = "abcd"，wordDict = ["ab", "bc", "cd"]，先删 "bc" 会剩下 "ad"，看起来拆不了，可实际上 "ab" + "cd" 是可以拆分的。字符串删除法的本质依赖于删除顺序，而顺序无法保证全局最优。

1.3 为什么这题适合动态规划

抛开具体代码，先想清楚问题本身的数学结构。定义布尔数组 dp[i] 表示字符串 s 的前 i 个字符组成的子串 s[0:i]（左闭右开区间）能否被字典中的单词拼出。

那么考虑第 i 个位置，如果存在某个 j，满足 j < i，并且 dp[j] 为 True，同时子串 s[j:i] 恰好是字典里的一个单词，那 dp[i] 就一定是 True。

这个递推式就是整道题的灵魂。它的意思是：我们不需要知道 s[0:j] 是怎么拆的，只要它能拆，且剩下那段 s[j:i] 恰好是一个合法单词，那整个前 i 个字符的串就能拆。这是一个非常典型的区间递推：大区间的解由某个前缀区间的解加一个单词片段组合而来。

有了这个递推式，问题的规模就变得可控了。s 的长度 n 最多 300，j 的取值有 n 种，用一张哈希表存字典可以在 O(1) 时间内确认子串是否在字典里，所以总复杂度是 O(n^2) 次子串查询。这是一个在 LeetCode 上非常舒服的复杂度。

2. 从暴力递归到动态规划：核心推导详解

2.1 先写一个能跑但一定超时的递归

理解动态规划最快的方式，是先写一个朴素的递归，然后亲眼看着它超时，再一步步优化。

朴素递归的想法是这样的：函数 dfs(i) 表示字符串从第 i 个位置开始能否被拆分。如果 i == n，说明已经走到字符串末尾，返回 True。否则，从 i 开始枚举下一步要切出的单词长度，看在字典里是否存在从 i 开始的子串，如果存在，就递归调用 dfs(i + len(word))。

def wordBreak(s, wordDict): words = set(wordDict) n = len(s) def dfs(start): if start == n: return True for end in range(start + 1, n + 1): if s[start:end] in words and dfs(end): return True return False return dfs(0)

这段代码逻辑完全正确，但提交到 LeetCode 上，遇到一个使用了大量重复子问题的用例就会爆炸。比如 s 是连续几十个 "a"，wordDict = ["a"]，此时 dfs(0) 会枚举 end = 1 到 n，每个分支又继续枚举，整棵递归树是指数级的。哪怕 s 只有 50 个字符，这个递归也要跑到天荒地老。

2.2 把重复计算缓存起来：记忆化搜索

递归慢的根源在于同一个 start 会被反复计算。这和我们做斐波那契数列时直接递归会遇到的问题一模一样。解决办法也简单，加一个缓存，记录已经计算过的 start 的结果。

from functools import lru_cache def wordBreak(s, wordDict): words = set(wordDict) n = len(s) @lru_cache(None) def dfs(start): if start == n: return True for end in range(start + 1, n + 1): if s[start:end] in words and dfs(end): return True return False return dfs(0)

加了缓存之后，每个 start 只会被真正计算一次，每次计算需要枚举 end，枚举过程中需要切片和查哈希表，所以总复杂度约为 O(n^2) 到 O(n^3) 之间，具体取决于切片复杂度。这个版本在 LeetCode 上已经能通过了，而且依赖的直觉很自然。

不过记忆化搜索毕竟带着递归函数调用的开销，而且在某些面试场景下，面试官看到你用 lru_cache 可能会多问一句：“你这算动态规划吗？” 所以更好的选择是把它改写成迭代式的动态规划，也就是自底向上的填表。

2.3 dp 数组的完整定义与转移方程

状态定义：dp[i] 表示字符串 s 的前 i 个字符组成的子串 s[0:i] 能否被拆分成若干个字典中的单词。

初始化：dp[0] = True。这里 dp[0] 表示空串，空串是当然可以拆分的，它是所有递推的起点。有些人看完这题不理解为什么 dp[0] 是 True，其实它就是数学归纳法的初始条件。如果没有这个初始条件，后面所有递推都无法启动。python 里切片 s[0:0] 就是空串，只是我们根本不会用空串去匹配字典，所以它只作为一个状态起点存在。

转移方程： dp[i] = True 当且仅当存在一个 j（0 <= j < i），使得 dp[j] == True 并且 s[j:i] 在 wordDict 中。

换句话说，我们在 i 之前找一个“切割点” j，把字符串前 i 个字符切成两段：前 j 个字符已经确定可拆，后 i - j 个字符是一个完整的单词。只要存在任何一个满足条件的 j，当前状态就成立。

这里要特别强调一个容易混淆的点：dp[j] 表示的是前 j 个字符可拆，和 s[j:i] 是否是一个单词，这两件事是相互独立的。前者是历史状态，后者是当前子串查询。这个拆分结构注定了我们遍历的时候要从短到长，保证 dp[j] 在计算 dp[i] 之前已经被确定。

3. 两种主流 DP 实现：切点枚举与单词枚举

3.1 写法一：外层遍历位置，内层枚举切点 j

这是最直观的写法，完全按照转移方程来写。外层从 1 到 n 遍历 i，内层从 0 到 i-1 遍历 j，查看 s[j:i] 是否在字典中。

def wordBreak(s, wordDict): 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]

这个版本很好理解，就是简单粗暴地枚举所有切割点。内层循环一旦找到一个可行的切割点，就马上 break 掉，不需要继续找。复杂度方面，外层 n 次，内层平均 n/2 次，每次需要切片 s[j:i]，切片本身的时间取决于子串长度，所以实际执行时间略高于 O(n^2)，但在 n <= 300 的约束下完全没问题。

3.2 写法二：外层遍历位置，内层遍历字典单词

另一种很常见的思路是反过来：与其枚举切割点，不如枚举字典里的每个单词，看它能不能“贴”在当前位置的尾部。

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

代码逻辑是：对于当前位置 i，逐个检查字典中的单词 w，如果 w 的长度不超过 i，并且前 i - len(w) 个字符可拆，同时 s 中从 i - len(w) 到 i 的子串刚好等于 w，那 dp[i] 就为 True。

这个写法的好处是理解起来非常符合“用单词拼接”的直觉，坏处也很明显：如果字典特别大，每次都要遍历整个字典。而且这里用 s[start:i] == w 来做子串比较，实际上是在重复切片和比较，效率不一定比枚举切点高。

3.3 两种写法的性能差异与选择依据

以下两组对比可以直观看出哪个更好：

n = 300，字典中单词个数 m = 1000，每个单词平均长度 10。

写法一：外层 i 循环 300 次，内层 j 循环最多也是 300 次，切片平均长度 150，总操作大约是 300 * 150 * 150 = 675 万次字符级操作。

写法二：外层 i 循环 300 次，内层遍历 1000 个单词，对于长度为 5 的单词只需要一个长度为 5 的切片比较，总操作大约是 300 * 1000 * 10 = 300 万次字符级操作，但因为有 30 万个单词匹配尝试，加上循环本身的开销，实际上并不见得快多少。

但如果 m 只有 10，写法一通常是更稳的选择，因为它循环次数少，且字典查询是 O(1)。如果 m 达到上万级别，写法二会非常吃亏，因为每次都要全量扫描字典。

另外，写法一有一个天然可优化点：我们可以提前计算字典中所有单词的最大长度 max_len，然后在内层枚举 j 时，只从 i - max_len 开始枚举。因为如果 j 离 i 太远，s[j:i] 的长度就会超过字典里最长单词的长度，它必然不可能是一个合法单词，查了也白查。这个优化能把内层循环次数压到 min(i, max_len)，收益非常明显。

def wordBreak(s, wordDict): 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]

这段代码加了最大长度剪枝后，复杂度显著下降。很多人写这题会忽略这个优化，但在面试中，如果你能主动提出来，面试官会认为你是有意识在做时间复杂度优化的人，而不是单纯背题解。

3.4 关于 dp[0] 和边界条件的常见疑问

有一个细节值得停下来单独说：dp[0] 为什么必须是 True？

假设没有 dp[0] = True 这行，那么计算 dp[len(word)] 的时候，如果 word 恰好等于 s 的前几个字符，我们需要检查 dp[0] 和 s[0:len(word)] 是否在字典里。dp[0] 如果不为 True，那么即使子串匹配成功，dp[len(word)] 也永远无法变成 True，后面所有状态都会跟着出错。

空串可以被拆分这件事，乍看之下有点违反直觉，但它是递推链条的地基。你也可以理解为：从空串出发，我们“已经完成了前面 0 个字符的拼接”。这种边界条件在动态规划里非常常见，斐波那契数列的 f(0) = 0、f(1) = 1 也是同样的思路。

边界上还有一个注意事项：内层循环里 j 的取值范围是 [0, i-1]，也就是说切割点最多到 i-1，必须保证 s[j:i] 是一个非空子串。如果 j == i，那 s[i:i] 是空串，空串不在字典里，查了也没意义。这个细节在写法一里通过 range(i) 天然规避了。

4. BFS 视角：这题不只有 DP 一种打开方式

4.1 把字符串拆解看成图的可达性问题

很多人不知道的是，单词拆分还可以用广度优先搜索来做。这个视角其实非常有助于加深对题目的理解。

把字符串的每个字符下标看作图上的节点，如果 s[i:j] 是字典中的一个单词，就相当于从节点 i 到节点 j 有一条有向边。那么问题就变成：从节点 0 出发，能否沿着这些有向边走到节点 n。

比如 s = "leetcode"，wordDict = ["leet", "code"]，那么节点 0 通过 "leet" 连接到节点 4，节点 4 通过 "code" 连接到节点 8，从 0 到 8 是可达的，所以答案是 True。

这种建模方式和很多图论题完全一致。理解这个模型之后，你会发现自己对 dp[i] 的理解也更通透了：dp[i] 就是“节点 i 是否从节点 0 可达”。

4.2 BFS 代码实现与细节

BFS 的做法是维护一个队列，初始时把 0 放进去。每次从队列里取出一个位置 start，如果 start == n，说明已经走到末尾，直接返回 True。否则枚举字典里的每个单词 w，如果 s[start:start+len(w)] == w，就把 start+len(w) 加入队列。

这里必须注意一个关键点：同一个节点可能会被重复加入队列多次，如果不做去重，极端情况下会超时。所以需要一个 visited 数组来记录已经访问过的节点。

from collections import deque def wordBreak(s, wordDict): words = set(wordDict) n = len(s) q = deque([0]) visited = set([0]) while q: start = q.popleft() if start == n: return True for w in words: end = start + len(w) if end <= n and s[start:end] == w and end not in visited: visited.add(end) q.append(end) return False

这套代码在 LeetCode 上是能通过的，而且思路很容易给面试官讲清楚。从图论模型到 BFS 的转换非常自然，比直接甩一段 DP 代码更有交流价值。

4.3 BFS 在某种情况下的致命弱点

不过 BFS 也有它尴尬的地方。如果字符串很长，而且字典里都是单个字符的词，比如 s 是几百个 "a"，字典是 ["a"]，那么节点之间的边就是相邻两个节点之间的顺序连接，从 0 到 n 是一条直线。这种情况下 DFS 和递归同样需要运行到很深，BFS 虽然不会重复计算，但依然要遍历几乎每一个可能的单词匹配，且每个单词都要做字符串切片比较。对于 LeetCode 的数据范围，BFS 是可以过的，但如果你在面试里用这个解法，面试官可能会追问一句：“如果字典很大呢？”

相比之下，DP 写法一的优化版因为限制了 j 的取值范围，在长字符串和短单词的组合下表现更稳定。时间复杂度上，DP 的写法一在应用 max_len 剪枝后是 O(n * max_len * avg_len)，而 BFS 的复杂度是 O(n * m * avg_len)，其中 m 是字典大小。字典很大时，BFS 的劣势非常明显。

所以我的建议是：面试优先讲 DP 解法，BFS 可以作为思维拓展提一嘴，展示你理解问题的角度足够多元，但最终落地的代码以 DP 为佳。

5. 实战踩坑记录与扩展思考

5.1 字典记得去重并转成哈希表

这道题的 wordDict 在 LeetCode 上不保证完全没有重复单词。虽然不需要专门写去重代码，因为放在 set 里自然就去重了，但如果你按列表的写法写 if word in wordDict，那每次查询都是 O(m) 的线性扫描，n 最多 300 时可能感觉不明显，但本来能压到 O(1) 的查询变成 O(m)，代码整体复杂度就退化到 O(n^2 * m) 了，这在海量测试用例下是有超时风险的。

一个小习惯：凡是这种需要反复判断某个元素是否存在于给定集合中的题目，一律先转 set。这个习惯不仅在这题适用，在做大多数字符串和哈希表类题目时都适用。

5.2 切片操作不是免费的

Python 的切片 s[i:j] 每次会创建新的字符串对象，一个长度为 300 的字符串切片 n 次，总时间成本并不像看起来那么微不足道。虽然 LeetCode 对 Python 比较宽容，但还是建议你用优化版的最大长度剪枝，来尽量减少不必要的切片次数。

如果确实追求极致性能，在某些语言里还可以用前缀哈希或者字典树进行子串匹配，但在这个题的数据范围下属于杀鸡用牛刀。面试时说清楚 Python 切片的代价，并主动选择剪枝方案，已经能体现你的代码敏感性了。

5.3 一个非常容易误判的经典样例

网上关于这题最常见的讨论样本就是 s = "catsandog"，wordDict = ["cats", "dog", "sand", "and", "cat"]。很多人第一眼看到这个词列表会觉得很迷惑：明明 "cat"、"cats"、"sand"、"and"、"dog" 都能从 s 里找到，为什么拼不出来？

我们实际拆一下：s 的前三个字符是 "cat"，前四个字符是 "cats"。如果选 "cat"，剩余部分是 "sandog"，其中 "sand" 可以匹配，剩下 "og" 无法匹配；如果选 "cats"，剩余部分是 "andog"，其中 "and" 可以匹配，剩下 "og" 也无法匹配。两种拆分顺序都死在 "og" 上，所以最终答案是 False。

这个例子很好地说明了为什么贪心、双指针、字符串删除这些方法会失败，因为你在每一步做出的选择，可能无法兼顾全局。而这种“当前位置的选择会影响到后续可达性”的结构，正是动态规划最擅长处理的问题。

5.4 从“能不能拆”到“怎么拆”：一道常见的变体题

掌握了基础版之后，有一个非常自然的扩展：如果 s 可以被拆分，要求输出所有拆分结果，应该怎么做？

这个变体在 LeetCode 上就是第 140 题。做法是把 dp 数组先当备忘录，然后用回溯去收集所有合法路径。具体来说，我们可以从 0 开始 DFS，每次走到一个位置 start，枚举找出所有可以匹配的单词及其对应终点 end，再把单词拼接到结果列表中，递归处理 end。最后利用 dp 记忆化剪枝，避免进入那些无法到达 n 的分支。这样既保证结果全部输出，又不会陷入指数级盲搜。

这个变体还能帮你反过来理解基础题：基础题的 dp 数组其实是一种“可达性表”，而变体题在可达性表基础上做路径回溯。把这两题连起来刷，动态规划在字符串切割问题上的应用基本就贯通了。

回到这题本身，我认为最有价值的不是那道递推式本身，而是你如何看待“状态”和“转移”。dp[i] 的定义、j 的枚举范围、以及为什么 dp[0] 必须是 True，这些想透了，整个动态规划的入门地基也会更扎实。如果你在面试里被问到这题，我都会建议先讲清楚“为什么贪心是错误的”，再给出 DP 的状态定义和转移方程，最后补上 BFS 作为拓展。这套组合拳打下来，基本很难被问倒。