单词接龙这道题，我刚刷完的时候心里只有一个念头：难怪它能成为面试高频题。它不是那种背模板就能过的题，也不靠什么冷门技巧，它考的是你能不能一眼把一个看似“字符串操作”的问题翻译成图论问题。力扣第 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 可以到 B，B 也可以回 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[i+1:] 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[i+1:] 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[i+1:] 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*a，replace只会替换第一次出现的a，结果还是*aa。所以要严格用切片拼接：w[:i] + "*" + w[i+1:]，这样位置才是精确的。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[i+1:] 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，可能就差这么一点“讲得明白”的距离。
单词接龙这道题，我刚刷完的时候心里只有一个念头：难怪它能成为面试高频题。它不是那种背模板就能过的题，也不靠什么冷门技巧，它考的是你能不能一眼把一个看似“字符串操作”的问题翻译成图论问题。力扣第 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 可以到 B，B 也可以回 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[i+1:] 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[i+1:] 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[i+1:] 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*a，replace只会替换第一次出现的a，结果还是*aa。所以要严格用切片拼接：w[:i] + "*" + w[i+1:]，这样位置才是精确的。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[i+1:] 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，可能就差这么一点“讲得明白”的距离。