最近在处理一个英语学习类工具的需求要做词链推荐给一个起始单词和一个目标单词每一步只允许改一个字母而且中间产生的每个词都必须真实存在于词表里最后问从起点到终点至少要经过多少步。刚开始以为这是个纯字符串题真正动手才发现这就是算法里非常经典的“单词阶梯Word Ladder”问题本质上是在一张隐式图上求最短的目标词链。不管你是想应付算法面试、做小游戏里的关卡生成还是单纯想弄懂BFS这个问题都值得拆开揉碎讲一遍。下面不绕弯子先讲怎么把文字游戏翻译成图论问题再讲为什么广度优先搜索是正解然后给出可以直接跑的代码最后聊聊我实际写的时候踩过的坑。如果对BFS已经比较熟可以直接跳到第4节看双向BFS的性能优化如果刚入门建议按顺序读完。1. 把文字拼图翻译成图论问题1.1 一个字母之差就是图上的一条边做过图算法题的人都知道图论题最难的往往不是算法本身而是建模。单词阶梯这题其实藏得很深你手里只有一个词表和一个字符串但一旦把“两个单词之间是否只差一个字母”定义成“是否存在一条边”整个问题就瞬间变成一张无权图。举个例子。词表是 [hot, dot, dog, lot, log, cog]起点是 hit终点是 cog。允许的变换是 hit - hot因为只需要把 i 改成 ohot - dot只需要把 h 改成 ddot - dog只需要把 t 改成 g。整个模型里根本不关心单词的意思只关心每个位置能不能替换成另一个字母并且替换结果恰好落在词表里。这样建模有个明显好处一旦图示化“最短目标词链”就是在求“从起点节点到终点节点的最短路径”而“每一步只改一个字母”天然对应一条权重为1的边。路径经过几个节点就是链上包含几个单词路径有几条边就是实际改了几次字母。很多后续优化都是建立在这个基础认知上的。1.2 节点集合由词表决定不会瞬间爆炸没接触过的人第一反应可能是26个字母单词长度也才5到6位这张图到底有多大其实节点数就是词表大小。词表有N个词每个词长度为L图的节点数就是N根本不会因为所有字母组合而爆炸。每条边连接两个只差一个字母的单词边数最坏接近N平方但真实词表里一般是稀疏图。这也是为什么要先做图论建模而不是直接暴力枚举所有字母串你只需要关心词表里出现过的词不需要关心那些拼出来但字典里根本不存在的字符串。把“节点边”这两个关键词锁定之后BFS的身份已经呼之欲出剩下的问题就是在这张隐式图上做最短路搜索。1.3 一层一层扩散才叫“最短”多走几个例子就会发现从起点往终点走第一层能到达的词通常有好几个第二层更多搜索空间像扇子一样展开。如果目标是求“最短”你希望以“层”为单位一圈一圈扩散而不是顺着某一条分支一条道走到黑。这个朴素直觉直接决定了算法选型后续选择BFS的代码结构也正是为了配合这种一层一层推进的天然特性。2. 为什么非BFS不可而不是DFS2.1 图层级扩散保证“首遇即最短”关键词是“层”。BFS的特性是所有距离起点为 k 的节点在第 k 轮被访问再由它们生成第 k1 轮节点。因为每前进一层就多改一个字母所以第一次遇到终点时所走的层数就是所有可能路径中最短的层数。这是BFS最根本的保证也是它在这道题里的不可替代性。DFS也能找到终点但它是沿一条分支一路走到底遇到死胡同再回头。它不按“离起点距离”的顺序探索节点很可能第一条找到的路径是七拐八弯的长路径你还要继续把所有路径都遍历完才能确定最短的那条。在词表规模稍大时这个代价真的很难接受。2.2 一个反例说明DFS为什么吃亏我用DFS写过一版递归实现试跑小词表。起点 hit终点 cog递归函数固定从第1个字母开始尝试替换结果先冲向 hit - hot - pot 这条支路再把 pot 的两个字母、三个字母都试完才回头等找到 cog 时已经绕了一大圈。换成BFS后所有一层候选、二层候选都是同批次展开任何一条分支都不会比别的分支探索得深太多。有人会说DFS可以用“当前最优解”剪枝但剪枝对单词阶梯并不友好单词之间的连通分支彼此纠缠你很难用一个可靠的上界砍掉大量子空间。所以在这个问题上正解几乎公认是BFS它不是“之一”而是标准答案。2.3 无权图最短路的一般原则相信你已经能看出来只要是“每条边代价相同”的最短路问题BFS就是标准答案Dijkstra反而有点杀鸡用牛刀。单词阶梯恰好是典型的无权图最短路。BFS的复杂度通常记为 O(VE)V是节点数E是边数。但后面我们会看到真正的性能瓶颈不是这个理论复杂度而是“如何高效找出一个词的所有合法邻居”这是接下来要展开的重点。3. 从0到1写一个能跑的BFS实现3.1 队列、访问标记、层数变量写BFS时要明确三样东西队列里存待扩展的单词visited标记是否访问过step表示当前扩展到的层数。层数变量是这题最容易写错的内容很多人把返回值搞差1是因为没分清“第几个单词”和“走了几步”。from collections import deque def ladder_length(begin_word, end_word, word_list): word_set set(word_list) if end_word not in word_set: return 0 if begin_word end_word: return 1 L len(begin_word) queue deque([begin_word]) visited {begin_word} step 1 # 当前队列里的词是第1层 while queue: for _ in range(len(queue)): word queue.popleft() for i in range(L): for c in abcdefghijklmnopqrstuvwxyz: if c word[i]: continue new_word word[:i] c word[i1:] if new_word in word_set and new_word not in visited: if new_word end_word: return step 1 visited.add(new_word) queue.append(new_word) step 1 return 03.2 层循环的 for 写法是灵魂很多初学者直接把 while queue 里poll一个处理一个这样表面也能跑但队列里会混入第1层和第2层的词你根本不知道当前处理到哪一层。“层”是BFS的灵魂所以代码里每次先固定当前队列长度用 for _ in range(len(queue)) 把当前层所有节点一次性处理完下一层节点入队step才加一。这样当扩展第 k 层时命中终点返回值自然就是第 k1 层的层号。这个细节写完之后最好多拿两个用例验证比如 begin_word 正好和终点只差一个字母看返回值是不是2。我自己刚开始学这个题时就是在这里吃了亏少写了一层循环结果只能返回“是否可达”根本拿不到最短长度。3.3 返回值到底是“词数”还是“步数”我习惯统一返回“链上单词个数”起点和终点如果相同返回1如果第一层就找到终点比如 begin_wordhot、end_worddot 且词表里有 dot第一层扩展命中链上有2个单词。如果你希望得到“改了几次字母”用返回值减1即可。面试或正式需求里一定要先和对方确认这个口径否则实现再正确也可能被误判。我自己曾经把“步数”和“词数”搞混联调时发现前端显示的阶数总是差1查了很久才发现是语义问题而不是算法逻辑问题。3.4 复杂度理论O(VE)实际瓶颈在找邻居如果先把整张图建好再BFS理论复杂度是O(VE)但建图本身往往要两两比较所有单词复杂度O(N平方乘L)词表一上万基本没法看。上面的实现没有预建图而是用“逐位替换26个字母”的方式实时生成候选邻居。每个入队单词会尝试 L 乘 26 个变形整体是O(N乘L乘26)词表长度通常5到15所以实时展开比两两建图轻量得多内存也更小。4. 双向BFS与实时扩词两个真正影响性能的决策4.1 单向BFS在深链场景下的软肋遇到很深的词链时单向BFS的搜索空间大约等于分支因子的深度次方。假设一个词平均有5个合法邻居深度为10最坏情况要扩展近千万级别的节点这已经非常可观。不是每道题都会卡这么死但词表一大、链条一深单向BFS很容易超时。如果你只写过几道简单迷宫题可能觉得这个量级无所谓。但单词阶梯的词表动辄几百上千字母替换规则又会制造大量分支真实的搜索空间比小迷宫大好几个数量级。这也是为什么这个题光会BFS还不够还要知道怎么优化搜索半径。4.2 两边同时挖中间相遇既然起始词和终点都给定一个很自然的想法是从起点往终点找的同时也从终点往起点反向找。两边每次只扩展当前候选中数量更少的那一侧当两个搜索区间相遇时最短目标词链就找到了。因为每一侧的搜索深度都减半总探索量从约 b 的 d 次方降到约2倍 b 的 d/2 次方收益非常明显。这个思想叫“中间相遇”在密码学破解、状态空间搜索里都用得很广。落到单词阶梯上它做的工作并不复杂维护两个集合哪边候选少就扩哪边每次扩展后看看生成的新词是否已经在对面出现过是则直接拼出完整链。4.3 双向BFS代码模板def ladder_length_bi(begin_word, end_word, word_list): word_set set(word_list) if end_word not in word_set: return 0 front, back {begin_word}, {end_word} dist_front, dist_back {begin_word: 1}, {end_word: 1} L len(begin_word) while front and back: if len(front) len(back): front, back back, front dist_front, dist_back dist_back, dist_front next_front set() for word in front: for i in range(L): for c in abcdefghijklmnopqrstuvwxyz: if c word[i]: continue new_word word[:i] c word[i1:] if new_word in dist_back: return dist_front[word] dist_back[new_word] if new_word in word_set and new_word not in dist_front: dist_front[new_word] dist_front[word] 1 next_front.add(new_word) front next_front return 04.4 为什么用dict而不是set如果用set很难知道交汇时两侧各自已经走了多少层。dict记录的是“这个单词到起点侧的距离”所以在发现 new_word 已经在对侧访问过时返回 dist_front[word] dist_back[new_word]正好把两个半程拼成完整链长。这里的加法也很容易差1建议写完直接用第3.3节的边界用例验证一遍。还有个隐藏细节每次循环前要判断 front 和 back 谁更小但交换后 dist_front 和 dist_back 也要同步交换。漏掉这一步的话双向BFS会退化成单向BFS加一个没用的反向集合既加了代码量又没拿到性能收益。4.5 什么时候不需要双向BFS如果词表很小或者目标词离起点非常近双向BFS会因为维护两侧数据而显得略繁琐。不过对单词阶梯这种题双向版本几乎是面试标准配置代码量只多一二十行所以我的默认实现都会直接写双向。只有在明确知道搜索深度很浅的场景我才会退回单向实现减少心智负担。5. 我踩过的坑和一些容易忽略的边界条件5.1 词表可能包含重复也可能包含起点本身用set接收词表后重复词会自动去重这是正确做法之一。但要注意如果begin_word本来就在词表里一定要先把它标记为visited否则你从初始节点绕一圈又回到自己虽然BFS不会无限循环但会徒增搜索范围。更隐蔽的是end_word不在词表时题目通常要求返回0而不是路径长度很多人会忘记这个前置检查。我还见过把起点终点大小写混用的真正常见的词汇都是小写在工程化时最好统一做 lowercase 预处理少踩一个雷就省一段调试时间。5.2 邻接表预构建还是实时扩词网上很多答案是先按通配符建邻接表。比如把 cat 放入at、ct、ca* 三个桶里同一个桶里的词两两互为邻居。建表复杂度O(N乘L)之后每次查邻居 O(L乘26)空间O(N乘L)。实际写题时实时扩词更短但在生产环境里如果同一个词表被高频调用比如英语学习App要反复计算不同起终点预构建邻接表一次、查询无数次会更划算。如果只是单次计算实时展开完全够用。在做性能对比时我发现通配符建表还有一个附带好处可以提前过滤掉那些根本没有邻居的孤立词减少无意义的BFS分支。缺点是写起来比实时扩词绕一些面试时如果时间紧张还是建议先用能跑通的实时版本再按需优化。5.3 调试时把“层”打出来看我调这类BFS时有个习惯在层循环开头打印当前层号、队列长度、第一个出队词。一旦发现step增长比预期慢说明访问标记或词表转换出了问题。亲眼看到扩层过程比瞪着眼睛看代码快得多。对于双向版本还可以分别打印两侧当前候选集合的大小确认“每次扩展较小一侧”是否真的生效。我记得有一次调试了很久发现 front 集合一直没有变小打印后才发现是因为字符集里包含了大小写字母生成出来的 new_word 和词表里的小写单词永远对不上。把输入统一转小写后代码立刻正常。这种问题靠眼睛看很难发现靠日志一眼就能定位。5.4 如果要求输出完整目标词链怎么办有时候需求不只问最短长度还要把整条链打出来。只需要在visited之外再维护一个parent字典记录每个词是从哪个词扩展来的。遇到终点后从终点一路回溯到起点反转就是完整路径。这里的parent可以在扩展时实时更新只要注意别覆盖已经走过的节点的父记录就行。这里有一个容易踩的坑双向版本如果想输出完整路径最省事的做法是固定单向BFS记录父节点或者只在扩展一侧时记录父节点另一侧只判断相遇不要两边都记录再拼接否则很容易出现方向不一致、回溯断链的问题。我在尝试两边都存parent时就遇到过拼接后路径中间缺一环的情况最后改成单侧记录才稳定。5.5 字符集假设别写死题面一般默认只有小写英文字母固定遍历a到z是安全的。但如果换成大小写混合字符集就是52个包含数字就是62个。最好把字符集大小作为输入参数不要硬编码。这个看着是小事在真实项目里最容易出问题因为词库来源一旦变化BFS结果就会从“稍慢”变成“漏解”。如果把字符集作为函数参数代码的复用面立刻宽很多同一个算法既能处理英文单词阶梯也能处理数字密码破解、验证码候选生成、自定义符号集的状态搜索。项目里的输入来源五花八门这种参数化设计往往能省下后面很多改造成本。5.6 从单词阶梯延伸到更多BFS场景理解了单词阶梯之后很多类似玩法都能看懂滑动拼图里的最少移动次数、魔方状态还原、游戏里的步数最短求解都可以抽象成“状态节点合法操作边无权图最短路”。你只需要把词表换成状态集合把“改一个字母”换成“执行一次操作”算法骨架几乎原封不动。这也是我一直推荐把BFS练透的原因它不是一个孤立的题而是一整类搜索问题的入口。从最简单的图层级展开开始再到双向缩短搜索半径这套思维迁移到其他领域也同样成立。等你把双向的细节吃透看到任何“给定起点和终点求最短变换”的需求第一反应就不会再是冥思苦想具体规则而是直接问自己状态节点是什么合法动作是什么边权是不是都为1。想清楚这三点方案基本就定下来了。