LeetCode 472 连接词

摘要

LeetCode 472「连接词」是一道看起来像字符串处理，实际上是典型“字典 + DP / DFS”综合题。
它非常容易写出“能跑但超时”的版本，也很容易在边界条件上踩坑。

这道题在真实业务中也并不陌生，比如：

• 搜索引擎里的复合词拆分
• NLP 中的分词与词典匹配
• 用户输入校验、黑白词组合判断

这篇文章会从最直觉的思路开始，逐步推到一个稳定、不超时、可维护的 Swift 解法，并给出完整 Demo 和测试示例。

描述

题目给你一个没有重复单词的数组words，要求你找出其中所有的「连接词」。

什么叫连接词？

一个单词，完全由数组中至少两个更短的单词组成。

注意几个隐藏点：

• 至少两个，不是一个
• 可以重复使用同一个单词
• 顺序是拼接，不是打乱

比如：

"ratcatdogcat" = "rat" + "cat" + "dog" + "cat"

这道题如果你只是“能不能拆分字符串”，那就是 LeetCode 139；
但这里是要对数组里的每个词都做一次判断，而且不能用它自己当素材。

题解答案

整体思路可以概括成一句话：

先把所有单词放进一个 Set，然后对每个单词做「能否由其他单词拼出来」的判断。

判断方式有很多，但工程上最稳的是：

• 按长度排序
• 逐个单词，用 DFS + 记忆化 或 DP 判断
• 判断时，暂时把当前单词从词典中“视为不可用”

这样可以避免：

• 自己拆自己
• 重复计算
• 深度递归导致的超时

题解代码分析

下面是一份完整、可运行的 Swift Demo，结构清晰，逻辑拆分明确。

classSolution{funcfindAllConcatenatedWordsInADict(_words:[String])->[String]{// 按长度排序，短词优先letsortedWords=words.sorted{$0.count<$1.count}varwordSet=Set<String>()varresult:[String]=[]forwordinsortedWords{ifword.isEmpty{continue}ifcanForm(word,wordSet){result.append(word)}wordSet.insert(word)}returnresult}privatefunccanForm(_word:String,_dict:Set<String>)->Bool{ifdict.isEmpty{returnfalse}letchars=Array(word)varmemo=Array(repeating:false,count:chars.count)funcdfs(_start:Int)->Bool{ifstart==chars.count{returntrue}ifmemo[start]{returnfalse}varcurrent=""foriinstart..<chars.count{current.append(chars[i])ifdict.contains(current){ifdfs(i+1){returntrue}}}memo[start]=truereturnfalse}returndfs(0)}}

为什么要先按长度排序

这是一个非常关键但容易被忽略的点。

如果你不排序：

• 长词先进入 Set
• 在判断时，很可能会用“更长的词”去拆“更短的词”
• 甚至出现自己拆自己的情况

排序后流程变成：

1. 先把短词放进字典
2. 再判断长词能不能由这些短词拼出来

这和真实世界里词典构建 → 复杂词分析的流程是完全一致的。

DFS + 记忆化在这里解决了什么问题

假设你有一个词：

"catsdogcats"

从第 0 位开始，有非常多的切分方式：

• cat | sdogcats
• cats | dogcats
• catsdog | cats（失败）

如果你不做记忆化，每个失败路径都会被反复计算。

memo[start]的含义是：

从start位置开始，已经验证过“拼不出来”，以后别再试了。

这一步是性能是否能过的关键。

为什么不用 DP 数组直接做

当然可以，但 DFS 在 Swift 里写起来：

• 更直观
• 更贴近“拆字符串”的自然思路
• 代码可读性更强

本质上，DFS + memo 和 DP 是等价的。

示例测试及结果

我们用题目里的示例来跑一遍。

letsolution=Solution()letwords1=["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]print(solution.findAllConcatenatedWordsInADict(words1))// ["catsdogcats", "dogcatsdog", "ratcatdogcat"]letwords2=["cat","dog","catdog"]print(solution.findAllConcatenatedWordsInADict(words2))// ["catdog"]

输出结果和题目预期完全一致。

时间复杂度

设：

• n是单词数量
• L是单词最大长度

单个单词的 DFS 最坏情况下是O(L^2)，
整体复杂度约为：

O(n * L^2)

在题目给定的约束下（总字符数 ≤ 1e5），是完全可以接受的。

空间复杂度

主要来自：

• Set存储所有单词
• DFS 的 memo 数组

空间复杂度约为：

O(n * L)

没有额外的高消耗结构。

总结

LeetCode 472 是一道非常典型的“工程型字符串题”，它考察的不是某个花哨算法，而是：

• 是否能正确建模问题
• 是否意识到“顺序”和“依赖关系”的重要性
• 是否能控制递归与重复计算的成本

在真实业务中，这类问题经常出现在：

• 搜索关键词分析
• NLP 分词系统
• 输入合法性校验
• 规则引擎与词典系统

如果你能把这道题写到结构清晰、逻辑稳、性能可控，那说明你已经不只是“刷题”，而是在用工程思维解决问题。