单词接龙这道题我刚刷完的时候心里只有一个念头难怪它能成为面试高频题。它不是那种背模板就能过的题也不靠什么冷门技巧它考的是你能不能一眼把一个看似“字符串操作”的问题翻译成图论问题。力扣第 127 题标签写着广度优先搜索但很多人在面试里第一反应却是回溯、DFS甚至有人往动态规划上想结果代码写了一百多行复杂度还是爆的。这篇“剑斩OFFER”我想把这道题的暴力美学完整拆一遍怎么建模、两种建图方式如何取舍、双向 BFS 为什么值得学、以及面试现场怎样把思路讲得又准又快。先说一个我带过的候选人最典型的翻车现场拿到题看到“最短转换序列”下意识就开始枚举所有可能换字母的路径等回溯写完一跑超时。然后换 DFS 尝试一层层往下搜还是超时。最后灵光一闪想到 BFS才勉强跑通但面试官已经在暗示“还有没有优化空间”了。这不是算法不会而是模型建立得晚了一步。其实这道题真正想考察的是你愿不愿意把“单词”当成“点”把“换一个字母”当成“边”。有了这个视角后面的代码只是把思路落到细节而已。1. 面试中被问到的第一反应为什么是 BFS 而不是回溯1.1 三秒建模把单词接龙翻译成图论问题先把题面翻译成人话给定一个起始单词 beginWord、一个结束单词 endWord以及一个词典 wordList。每次只能改动一个字母改出来的中间结果必须出现在 wordList 里。问从 beginWord 到 endWord最少经过多少个单词包含两端才能到达。注意你手里的材料每个单词是一个节点两个单词之间如果只差一个字母就存在一条无向边。这样一来问题就变成了赤裸裸的“无权图中求最短路径长度”。而无权图求最短路径最合适的就是 BFS。为什么因为 BFS 的层序遍历天然按距离递增展开当你在第 k 层第一次遇到 endWord 时前面所有层都已经验证过“到不了”所以这个 k 一定是全局最小步数。这个性质叫 BFS 的最短路径性本质是队列先进先出 分层遍历共同保证的。我习惯在面试开头十秒就说破这件事“这是一个无权图上的最短路径问题所以我会用 BFS并且可以进一步用双向 BFS 优化。”这句话一说出来面试官基本就放心了因为他知道你已经跳出了字符串细节看到了问题的骨架。后面写代码反而快。还有个概念要区分清楚题目返回值到底是“转换次数”还是“序列长度”。力扣 127 的英文原题是 “shortest transformation sequence length”中文题面基本都按“序列长度”解释也就是把 beginWord 本身也算进去所以返回值是“边数 1”。比如 hit - hot - dot - dog - cog能看出转换了 4 次但答案写 5。很多人自测对提交不对往往就是差在这个语义上。1.2 回溯、DFS 与 DP为什么看起来都能做其实都不对先说回溯。回溯是枚举所有可能路径的它天然适合“输出所有解”或者“判断是否存在解”的问题但用来求最短路径时需要走完一条完整路径才能得到一个可行解而且不能保证第一个解就是最优解。你要想得到最短路径就得维护全局最小值把所有路径都枚举完那复杂度就指数爆炸了。在这题上一个单词最多 10 个字母单词表可能到几千个词随便一条路径也能延伸出天文数字的组合回溯基本没有活路。DFS 其实可以做但它的“天性”是尽量往深处走走到死胡同再回头。你当然可以写一个带min_distance剪枝的 DFS或者用迭代加深但那已经是另一种为了弥补 DFS 缺陷而做的改造了。本质上在无权重图中想求最短BFS 是语义最匹配的工具强行用 DFS 等于用手帕拧螺丝能拧但非常别扭。至于动态规划那是另一个常见误区。有些同学看到“最短”两个字就条件反射设dp[word] 到达该词的最短长度然后试图从所有邻居转移过来。问题在于单词之间的转换图完全可能有环A 可以到 BB 也可以回 A局面并不具备天然的拓扑序。你没法保证计算dp[B]的时候dp[A]已经是最终值了。想硬做也不是不行那就是 Bellman-Ford 式的反复松弛等它迭代到收敛复杂度比 BFS 高得多代码也更啰嗦。所以这道题的正确打开方式只有一条路用 BFS 老老实实按层扩散。你可能觉得 BFS 太“暴力”了一层一层扫过去一点技巧都没有。但恰恰是这种不带任何启发式、不加任何剪枝的均匀扩散能确保第一碰到就最短。这就是我标题里说的“暴力美学”——把暴力用在组织良好的数据结构上暴力本身就成了最优解。2. 从单词到图的映射两种邻边构造方式与取舍2.1 逐字符哈希代码最直白但每一层的展开代价要算清楚第一种建图方式也是最容易想出来的对当前单词的每个位置尝试替换成 26 个字母中的任意一个然后判断新词是否在 wordList 里。用集合存储 wordList判断复杂度就是 O(1)。伪代码如下from collections import deque def ladderLength(beginWord, endWord, wordList): word_set set(wordList) if endWord not in word_set: return 0 queue deque([(beginWord, 1)]) visited {beginWord} while queue: word, step queue.popleft() for i in range(len(word)): for ch in abcdefghijklmnopqrstuvwxyz: if ch word[i]: continue nxt word[:i] ch word[i1:] if nxt endWord: return step 1 if nxt in word_set and nxt not in visited: visited.add(nxt) queue.append((nxt, step 1)) return 0说句实话我最初写这道题时就是这个版本干净、好懂而且不需要任何预处理。但它的代价很隐蔽每从队列里弹出一个单词就要做长度 × 26次拼接和集合查询。如果单词长度是 10一层的分支因子理论上有 260几千个词铺开以后中间层的规模会涨得非常快。注意我上面在循环里提前做了一个nxt endWord的判断这样和把 endWord 当普通节点处理最终再检测效果是等价的但提前返回能省一层循环。写的时候要小心别把步数加错因为队列里当前层的 step 是 k换一次字母等于走到下一层所以答案是step 1。2.2 预处理通配符字典把“找邻居”从 26 次扫描变成一次哈希第二种思路更聪明也是官方题解里常用的提前为 wordList 里每个单词生成所有“挖掉一个字母”的通配模式比如hit会产生*it、h*t、hi*三个模式。然后用一个字典把每个模式映射到能匹配的所有单词。BFS 过程中当前单词只要也挖掉一个字母查字典就能直接拿到所有一步可达的邻居完全不用逐个字母试。from collections import deque, defaultdict def ladderLength(beginWord, endWord, wordList): word_set set(wordList) if endWord not in word_set: return 0 pattern_map defaultdict(list) for w in word_set: for i in range(len(w)): pattern w[:i] * w[i1:] pattern_map[pattern].append(w) queue deque([(beginWord, 1)]) visited {beginWord} while queue: word, step queue.popleft() if word endWord: return step for i in range(len(word)): pattern word[:i] * word[i1:] for nxt in pattern_map.get(pattern, []): if nxt not in visited: visited.add(nxt) queue.append((nxt, step 1)) return 0这里有个容易翻车的点生成模式时千万别用string.replace()即使指定替换次数也可能出错。比如单词是aaa你在第 0 个位置做通配想得到*aa用replace(a, *, 1)恰好会得到*aa看起来没问题但第 1 个位置时想得到a*areplace只会替换第一次出现的a结果还是*aa。所以要严格用切片拼接w[:i] * w[i1:]这样位置才是精确的。2.3 两者怎么选数据规模决定一切两种方式没有绝对优劣我根据实际刷题经验给一个判断维度维度逐字符哈希通配符预处理预处理时间无O(N * L)额外空间无O(N * L) 的模式映射每层展开代价长度 * 26 次查询长度次哈希查询代码复杂度低中适合数据规模单词短、规模小单词长、单词表大力扣这道题的范围是 wordList 最多 5000 个单词单词长度最多 10两种都能过。但如果单词表更大或者单词更长逐字符版的长度 × 26就会变成明显的常数瓶颈预处理版更稳。反过来如果面试官只要求给出一个能跑的版本逐字符哈希无疑是思路最清晰的选择写起来也不容易出边界 bug。我个人的习惯是第一时间先给逐字符哈希版作为“正确性优先”的答案然后主动说一句“如果规模再大我可以预处理通配符来降低每层扩展常数”这样既展示了代码能力又展示了优化意识面试官通常很吃这一套。3. 双向 BFS 压榨性能为什么指数扩张最怕两头会师3.1 单向 BFS 的瓶颈中间那层才是灾难普通人能写出 BFS 已经算合格但想拿到高分就必须理解为什么单向 BFS 在这道题里会“中间爆炸”。假设从 beginWord 出发每层能扩张出来的新词平均有 b 个b 是分支因子目标在距离 d 层的位置。单向 BFS 需要访问大约1 b b² ... b^d个节点最后一层的量级是 b^d 的。真正把内存和计算拖垮的不是起点附近那几层而是接近终点的那几层。分支因子稍微大一点比如 10搜索层数到 6 层时单层就有百万量级这不是开玩笑。双向 BFS 的思路很简单粗暴别让一边水波从起点一路推到终点而是从起点和终点同时各推一层直到两边的波前相遇。这样原本要推 d 层现在两边各推 d / 2 层就碰头了总访问节点数量从 b^d 的量级变成2 * b^(d/2)的量级。指数从 d 降到 d/2对性能来说是质变。3.2 双向 BFS 的代码实现与几个易错细节双向 BFS 的写法有两种一种是维护两棵 BFS 树各自带 visited 集合另一种是用两个集合记录当前层并轮流扩展。我个人推荐集合写法它比显式队列更直观判断“相遇”也方便。下面是完整实现def ladderLength(beginWord, endWord, wordList): word_set set(wordList) if endWord not in word_set: return 0 head {beginWord} tail {endWord} visited_head {beginWord} visited_tail {endWord} step 1 while head and tail: if len(head) len(tail): head, tail tail, head visited_head, visited_tail visited_tail, visited_head next_level set() for word in head: for i in range(len(word)): for ch in abcdefghijklmnopqrstuvwxyz: if ch word[i]: continue nxt word[:i] ch word[i1:] if nxt in tail: return step 1 if nxt in word_set and nxt not in visited_head and nxt not in visited_tail: next_level.add(nxt) visited_head.add(nxt) head next_level step 1 return 0这段代码里有三个细节不注意就会写歪。第一个细节是每轮要“从小的集合向外扩”。如果 head 集合已经比 tail 大就交换两者并且把两侧的 visited 集合也一起交换。原因很简单你希望每次扩散的波前面最小这样下次出队的节点数量最少。这里交换的是整个方向的镜像不是单纯换内容。第二个细节是nxt in tail的相遇判断必须在入队前做。因为从 head 里取出的单词生成一个词如果这个词恰好在 tail 里说明两边已经短路了返回step 1。这个step 1表示当前层再走一步就能连上另一侧是双向 BFS 的步数计算核心别把它跟普通 BFS 的step搞混。第三个细节是nxt not in visited_tail也要检查。很多初学者只查visited_head结果把对面已经访问过的节点又塞进了当前节点的下一层导致两个波前互相穿过却一直碰不上。虽然在某些写法里不会立刻出错但会在后续层产生重复计算甚至死循环风险。3.3 步数不会翻倍的保证有点同学会有顾虑两边各走一半最后步数是不是要加起来实际上不用。我们维护的 step 是“从 beginWord 方向算起的当前层深度”每次 head 换成 next_level 时 step 加 1等检测到 nxt 在 tail 里直接返回 step 1 就表示了 beginWord 侧走到 head 层再走一步落到 endWord 侧这个完整路径长度。这里的关键是我不需要关心 endWord 侧内部已经走了多少层因为对侧已经把那段路在 visited_tail 和 tail 里准备好了只要桥接过去总路径就是最短的。这样算出来的答案和单向 BFS 从起点一路数出来的层数严格一致不会多也不会少。我自己第一次实现时就在这多虑了半天后来拿小数据调试过才彻底放心。4. 边界条件、复杂度计算和现场讲题节奏4.1 边角案例提交错一次往往就错在这里这道题的隐藏坑不少我整理成一张自查清单场景正确行为常见错误endWord 不在 wordList直接返回 0继续 BFS最终返回 0 但效率低beginWord 就是 endWord返回 1如果题意允许返回 0beginWord 本身也在 wordList起点入队时标记访问防回头起点被再次从邻居访问步数错误wordList 为空直接返回 0进入空搜索超时单词长度为 1每种模式只有一个字符的通配逻辑不变下标或切片越界特别是第一行很多人写代码时假设 endWord 一定存在于 wordList结果一轮测试挂掉。其实题面里说得很清楚如果 endWord 不在 wordList 中返回 0。这应该在函数最开头就检查掉既能省时间也让后续逻辑更清晰。第二行比较微妙。如果 beginWord 和 endWord 相同按字面理解转换序列长度就是 1。很多解法不会专门处理因为一般测试数据不会这么给但面试时你可以提一嘴“如果考虑相同的情况应该返回 1”这种主动性往往加分。4.2 复杂度到底怎么算面试官真实想听什么假设单词表长度为 N单词平均长度 L分支因子为 b。逐字符哈希版的 BFS每个节点最多展开26 × L个候选词总访问节点数在最坏情况下是 O(N)因为 visited 保证每个词最多入队一次。再加上每步的哈希查询整体时间近似O(N × L × 26)空间 O(N)。预处理通配符版建表耗时 O(N × L)BFS 过程中每个词生成 L 个模式并查表整体时间近似 O(N × L)不过空间也多付出了 O(N × L) 的映射关系。在本题的数据范围内这种“空间换时间”通常是划算的。双向 BFS 的复杂度描述要更谨慎。它没有本质上改变最坏复杂度上界仍是 O(N × L × 26)但实际运行中搜索层数从 d 变成 d/2访问节点数量从 b^d 降为2 × b^(d/2)对指数扩张的搜索空间是一个巨大的常数层面改善。面试里你把这个区分讲清楚会显得理解到位。我见过很多候选人把复杂度背成“O(N²)”一问为什么就卡壳。正确姿势是先说明 visited 保证了每个单词最多被访问一次所以节点层面是 O(N)再说明每次展开需要枚举若干个候选邻居因此额外乘一个与 L 和 26 有关的常数。这样逻辑闭环面试官很难追问倒你。4.3 现场讲题的节奏先讲模型再讲优化最后再写码我总结了一个四段式讲题节奏对这道题特别适用。第一段是模型。开口就说“这是无权图最短路单词是点一步变换是边因此用 BFS”这个定位不超过十五秒。第二段是为什么。简单对比 DFS 会枚举所有路径、DP 不适用带环图一句话带过即可不用展开太多目的是让面试官知道你做过选择而不是只会背模板。第三段是优化。在给出朴素 BFS 思路后主动提到两个优化点一是用通配符预处理降低每层分支常数二是用双向 BFS 降低搜索深度。这里可以先问一句“需要我写朴素版还是直接写优化版”很多面试官会让你直接写优化版那就顺手展示双向 BFS。第四段才是写代码。写的时候不要沉默每写一个关键判断都解释一句比如“endWord 不在字典里直接返回 0”“这里交换集合是为了永远从小的波前扩散”“nxt 出现在对侧时返回 step 1”。这种边说边写的习惯在面试里的观感远好于闷头敲完再解释。5. 从 127 到同款题隐式图 BFS 的一鱼多吃5.1 换汤不换药的几道题这道题真正值钱的不是答案而是“隐式图 BFS”这个模型。所谓隐式图就是题目没有直接给你一幅图但你可以把每个状态当成节点、把每个操作当成边然后在这个虚拟图上跑搜索。力扣里有一批题都是这个套路题目相似点差异433 最小基因变化与 127 几乎同构基因序列固定 4 位字符集只有 4 个752 打开转盘锁同样是 8 个状态变量上的隐式图最短路多了死亡数字禁止节点要提前排除909 蛇梯棋BFS 求最少掷骰子次数有跳变边要处理“走到某个格子后瞬移”102 二叉树的层序遍历BFS 按层计数的思想这题是显式树结构比较简单以 433 为例你可以把基因字符串当节点每次变异一个位置就是一条边宽度优先找到最少变异次数。代码框架和 127 基本一样只是把 26 种字母换成了 4 种。所以我一直跟同学说别孤立地刷题把 127 吃透等于给 433、752 这类题买了一份保险。5.2 一个值得长期保留的判断习惯刷多了之后我形成了三个条件反射分享给你参考第一看到“最短”“最少”“最少步数”这类词优先想无权图 BFS 或 Dijkstra先判断图的边权是不是都一样。边权都是 1那 BFS 就是最优解。第二看到“状态转换”“每次只能改变一个元素”这类描述大胆把状态打包成节点。不管状态是一段字符串、一个棋盘还是一个数组只要操作前后能互相转化就能构造隐式图。第三BFS 代码出结果后多问一句“能不能双向”。搜索空间是否呈现从起点到终点的单向爆炸如果是双向 BFS 基本稳赚不赔。对这题来说双向 BFS 不是炫技是真的能省下一大截时间和空间值得每一次都写。我刷了两遍这道题第一遍只追求通过第二遍逼自己把单向、双向、通配符预处理三个版本都写完并对比性能和代码量。说实话第二遍的收获远比第一遍大。如果你也卡在“会做但讲不清楚”的尴尬里我强烈建议你像我这样把这道题刷厚一点先跑通朴素版再优化再对着想象中的面试官讲两遍。你的下一个 offer可能就差这么一点“讲得明白”的距离。
