刷LeetCode的都知道472这道连接词在热门题单里经常和单词拆分系列放在一起但它的坑比139、140多一层字典不是提前给你的得从输入数组里自己筛。我在周赛430前后又把它翻出来重做了一遍发现很多人卡在到底该用DFS还是DP为什么必须先排序空串怎么处理这几个地方。这篇就把我完整思考链路和最终AC代码一起放出来给正在刷动态规划和字符串题的朋友做个参考。1. 题面精读连接词到底在考什么先看原题给的定义给定一个不含重复单词的字符串数组words请你返回其中所有的连接词。连接词的定义是由数组中至少两个较短单词拼接而成的单词。这个至少两个很关键意味着目标单词至少要从字典里拼两次而且每次选用的单词都比它短——严格短于它。我见过有人用wordBreak的模板直接套结果把自己也放进了字典导致一个词自己拼自己判成 true这是新手最容易犯的错误。题目给的标准示例很有代表性words [cat,cats,catsdogcats,dog,dogcatsdog, hippopotamuses,rat,ratcatdogcat] 输出[catsdogcats,dogcatsdog,ratcatdogcat]注意hippopotamuses不是连接词因为数组里没有任何一个单词能构成它的前缀哪怕它本身很长。这说明长不是关键能否被不断拆分成字典里的短词才是关键。这道题的考点拆开来看其实很清晰字符串切分 / 拼接的枚举能力动态规划状态设计或者等价的记忆化搜索对输入数据做预处理排序以简化合法性判断集合或哈希表的高效查找它本质上就是LeetCode 139 单词拆分的变体区别在于139的字典是现成的472的字典需要你在遍历过程中动态构建。一旦想通这一点解题路径就非常明确了。2. 第一版暴力思路为什么它一定超时我在第一次见到这道题时第一反应是枚举所有组合把words两两甚至三三拼接看看拼接结果是否存在于原数组。这个思路方向没错但复杂度完全不可控。假设数组长度为 n平均单词长度为 L。如果只考虑两个词拼接要枚举 O(n²) 对组合每组拼接字符串长度 O(L)再用哈希表判断结果是否存在整体 O(n²L)看起来还能接受。但要拼出像ratcatdogcat这样的词它是由三个单词拼成的这时候枚举所有三元组就是 O(n³)更长的连接词甚至需要更多段整体退化到指数级。还有个更隐蔽的问题你没法提前知道一个连接词需要拆成几段。catsdogcats可以拆成catsdogcats但你枚举两两组合的时候根本不会发现它因为catsdogcats不在任何一对组合的结果里。除非你枚举所有 k 段组合直到 k 等于最大可拼段数这个枚举量对 n1000 的规模就是天文数字。所以暴力拼接这条路理论上成立实际上走不通。真正合理的思路是换方向不主动拼而是对每个词做减法——判断它能不能被拆成字典里已有的短词。判断一个词能否被拆分的标准方法就是139题的动态规划我们只是需要先把字典准备好。这个先拼后查到先查后拆的思维反转是这道题和单纯字符串拼接题最大的分水岭。3. 排序加长的妙处它同时解决了两个要命的问题如果直接对原始words数组做wordBreak动态规划会立刻撞上两个问题自我匹配判断cat能不能由数组里的词拼成时把cat自己也放进字典cat由cat拼成会被误判为 true。当然你可以在代码里特判不能用当前词本身但这样会引入很多边角逻辑。等长词互拼ab和abab这种长度不同的还好说要是两个词长度相等比如aab和aba它们谁也拼不出谁但如果都放进字典再互相查容易混乱。排序按长度从小到大处理这两个问题就自动消失了。核心思想是对每个词做拆分判断时字典里只保留那些已经处理过的、严格更短或等长的词——实际上因为我们按长度从小到大遍历处理当前词时字典里全都是长度小于等于当前词的前驱词而长度相等的词不可能互相拼成除非有词由另一个等长词加空串拼成空串我们后面会说怎么处理所以本质等价的说法是字典里只有更短的词。这里我特别强调一下这个贪心的合法性wordBreak判断一个长词能不能拆成短词拆出来的片段一定严格短于原词。比如判断dogcatsdog是否能拆分参与拆分的片段最多是dog、cats这样的短词绝不可能等于它自己也不可能比它长。所以当你按长度排序后处理到某个词时所有可能参与拼它的词都已经处理完毕可以放心加入字典。这个排序策略还有一个额外好处——它为后续的剪枝提供了最长单词长度指标。处理流程可以这样写按长度从小到大排序 words 初始化一个集合 dict用来存放已经确认可以成为字典词的短词 初始化一个变量 maxLen记录当前 dict 里最长单词的长度 遍历排序后的每个词 w: 如果 w 能由 dict 中的词拼成wordBreak 判断且 dict 非空: 把 w 标记为连接词 把 w 加入 dict 更新 maxLen注意一个细节dict里放的是所有已经遍历过的词不仅仅是连接词。比如示例里的cats、dog、cat都会进入字典因为它们是后续连接词的原材料。有些题解会误以为只需要把连接词放进去这是不对的——如果只放连接词dogcatsdog需要拆成dogcatsdog三个片段里cats本身确实是个普通词但它不在连接词列表里你必须保留所有短词。4. 动态规划状态设计dp[j]被谁拼出来这里我采用经典的wordBreakDP但需要改一个地方切分点的枚举范围可以用maxLen剪枝。状态定义是这样的dp[i] 表示当前单词 w 的前 i 个字符能否被 dict 中的单词拼接而成 初始化 dp[0] true空串当然能被拼出来它是递归基 对于每个 i枚举切分点 j 如果 dp[j] 为 true并且 w[j:i] 存在于 dict 中 那么 dp[i] true用dogs和字典[dog, s]来走一遍虽然示例里没有s我只是举例dp[0]true然后 j0w[0:3]dog在字典里dp[3]true接着 i4枚举 j3w[3:4]s在字典里dp[4]true所以dogs可以被拼成。这个 DP 是典型的前缀递推每个字符位置只依赖更靠前的位置和完全背包问题长得非常像。更通俗地说你可以把dp[i]理解成台阶能不能走到w[j:i]就是一步跨出去的距离这个距离必须恰好等于字典里某个单词的长度且内容匹配。在我实际写的 C 版本里为了配合maxLen剪枝内层循环的写法有些讲究bool canForm(const string word, unordered_setstring dict, int maxLen) { int n word.size(); vectorbool dp(n 1, false); dp[0] true; for (int i 1; i n; i) { // 枚举切分点 jj 必须距离 i 不超过 maxLen // 同时保证 j 到 i 这段长度至少为 1 for (int j max(0, i - maxLen); j i; j) { if (!dp[j]) continue; if (dict.count(word.substr(j, i - j))) { dp[i] true; break; } } } return dp[n]; }j从max(0, i - maxLen)开始枚举非常关键。如果不限制就需要枚举从 0 到 i 的所有位置每个位置再来一次substr时间复杂度是 O(L²) 次字符串截取和哈希查询。加了maxLen之后每个位置最多枚举min(maxLen, i)个切分点而maxLen又远小于很多长单词的长度常数优化非常明显。Python 版本的核心逻辑一模一样只是写起来更短def can_form(word: str, word_set: set, max_len: int) - bool: n len(word) 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 word[j:i] in word_set: dp[i] True break return dp[n]我刚才特意保留了dp[0] True这个初始化但主流程里必须保证字典非空才去判断一个词是不是连接词。理由很简单如果字典为空dp[n]的结果一定是 false因为你不可能拼出一个非空单词但dp[0]恒为 true容易让人误判。我在加这个判断时也栽过一次输出里混进来一个短单词排查很久才发现是空字典问题。5. 剪枝优化与边界情况把时间从超时拉到及格线这道题数据规模是数组长度不超过 1000单词长度不超过 30看起来不大但如果不加任何剪枝最坏情况下计算量也不小。我在AC之后故意试了下什么优化都不加的版本跑是能跑过但耗时差了好几倍。对刷题来说过了就行但对追求稳定性能的人来说下面几个优化值得做。第一招就是用上面的maxLen限制内层循环。这里还有个小技巧每次处理完一个新词后maxLen应该更新为该词长度和当前maxLen的较大值。这样随着遍历的进行maxLen逐渐变大但永远不会超过已经处理过的单词的最大长度切分点枚举范围始终是当前字典最长词的长度而不是越来越大的当前词长度。第二招是提前跳过太短的词。一个词要成为连接词至少要由两个词拼成所以长度小于 2 的词比如单个字符理论上不可能成为连接词除非有空串参与——我们后面说空串的标准处理。当然这个剪枝对性能影响不大但能帮你避免不少逻辑上的自我怀疑。第三招是substr的调用次数。C 里substr有拷贝开销我实测对长度 30 的单词影响很小但如果单词长度放大到几百这个开销就不可忽略了。另一个做法是用 Trie 树替代哈希集合边扫描单词边走前缀树可以省掉字符串切片和哈希计算代价是实现复杂度上升。对 472 这道题的官方数据规模来说哈希集合 substr 完全够用我建议先跑通再考虑 Trie。边界情况是这道题最容易出问题的地方我整理成一张表方便对照场景输入示例正确处理数组为空[]输出空数组只有一个单词[a]输出空数组因为长度小于2且字典为空空字符串[, a, ab]空串进入字典后任何词都能用空串原词拼成所以要去掉空串再判断重复单词题目保证无重复但遇到重复应去重哈希集合天然去重所有词都是短词[a,b]没有连接词输出空数组一个词由自身加其他词拼成[ab, a, b]无此情况长度相等场景需要排序规避空串这个坑值得单独说。words里如果包含空字符串直接放进字典那任何单词都能通过 单词本身拼成导致误判。标准解法是在遍历前把空串从数组里剔除单独处理。LeetCode 官方测试里确实有空串的场景我最初没处理提交直接栽了一次。还有个顺序输出的问题题目返回数组不要求保持原顺序所以按排序后顺序收集没问题。如果你有强迫症想按原顺序输出可以先记录每个单词的原始下标最后排序回来再返回反正也不贵。6. 从472到单词拆分全家桶一个思路吃透一类题472做完之后我复盘时发现字符串拆分类的题其实有一个共同的祖传套路把握住之后刷题效率高很多。这个套路分三层第一层是基础的wordBreak判定问题代表题 LeetCode 139。给你一个字符串和一个字典判断能否拆分。解法就是我上文写的 DP 模板没有第二层那些自己构建字典的问题。第二层是输出所有拆分方案代表题 LeetCode 140。在139的DP基础上加一个回溯收集路径。472的核心判断其实和139一模一样只是字典需要动态维护。这也是为什么很多人说472是139的进阶版——你需要先理解139的DP才能理解472的动态字典。第三层是把字典本身作为考点代表题就是今天说的472还有它的近亲 LeetCode 472 变体最短单词编码LeetCode 820等。这类题的共性是有序处理 增量维护哈希集合/Trie每一步操作都依赖于之前已经处理完的数据排序是这类题的灵魂。我推荐的刷题顺序是先做139彻底理解 DP 状态怎么推再做140理解如何从布尔 DP 升级成路径搜索最后做472感受动态字典 排序的威力。三步走下来字符串拆分这个分支基本就拿下了。如果还想更进阶一点可以研究一下用 Trie 优化canForm的实现把字典建成 Trie在扫描word的过程中同时走 Trie 节点一旦走到叶子就相当于匹配了一个单词可以触发一次 dp 状态更新。这个写法能省掉substr和哈希查询单次判断复杂度从 O(L×maxLen) 降到 O(L×avgLen) 量级不过实现细节比哈希版多不少适合作为延伸练习。我自己目前日常刷题还是优先写哈希版因为可读性好、调试容易。遇到极端大数据比如单词长达几千才会考虑换 Trie。刷题这件事先保证思路对、代码对再谈性能优化。最后分享一个我个人的小习惯这类需要排序和动态字典的题我会把字典里应该放什么和当前词能不能被拼出来这两个问题分开想清楚再动手写。很多人卡住是因为把这俩混在一起写出来的代码既想用字典判断当前词又想把当前词加进字典状态互相污染。其实只要在代码里把判断和加入分成两个步骤先判断后加入问题就豁然开朗了。472这道题我做完之后对139、140、820这几道题的理解都跟着通透了不少花一小时重刷一次不亏。