1. 题目拆解：单词接龙到底在考什么
先把这个经典题目的背景说清楚。LeetCode 127题“单词接龙”是图论与搜索领域的高频考题，也是BFS（广度优先搜索）算法的典型应用场景。题目本身的描述很直观：给定一个起始单词beginWord、一个结束单词endWord以及一个字典wordList，要求找到从起始词到结束词的最短转换路径长度，每次只能改变一个字母，且转换后的中间词必须存在于字典中，起始词本身不算在字典里但可以作为起点。
这道题第一次见的人往往会觉得“这跟图有什么关系”？实际上它就是一个标准的无权图最短路径问题。把每个单词看作图中的节点，两个单词之间如果只差一个字母就有一条边，那么问题就转化为“从beginWord节点走到endWord节点的最短路径长度”。节点数最多有5000个左右（按题目的约束），单词长度最长10个字母，暴力穷举所有转换路径是铁定超时的，需要借助BFS来保证“首次到达终点的路径一定是最短路径”这个性质。
为什么BFS能做到这一点？因为BFS是按层逐层扩展的。从起点出发，第一层是所有只差一个字母的单词，第二层是由第一层单词再改一个字母能到达的单词，依此类推。当某层第一次出现endWord时，当前层数就是最短路程，这也符合“无权图最短路径用BFS”的通用结论。DFS（深度优先搜索）不适合这道题，因为它会一条路走到黑，需要回溯尝试所有路径才能找到最短路径，时间复杂度是指数级的，在5000个节点的图上基本跑不动。
这道题在LeetCode热门100题里也占有一席之地，很多面试官喜欢拿它来考察候选人对BFS的理解深度，以及能否在基础BFS上做优化。接下来我会先给出两种经典写法的基础讲解，重点放在实现细节和踩坑点上，最后再聊聊双向BFS为什么快、快多少、什么情况下该用哪种。
2. 解法一：标准BFS为什么是首选
2.1 建图还是不建图？这是个关键选择
很多初学者拿到这道题的第一反应是先把字典里所有单词两两比对，建立邻接表，然后再在图上跑BFS。这个思路本身没错，但两两比对的时间复杂度是O(N²·L)，N是字典大小（最多5000），L是单词长度（最多10），最坏情况下要做25万次字符串比较，虽然也能勉强跑完，但在面试中显然不是最优解。
更普遍的做法是“不显式建图”，直接基于“改一个字母”的规则动态找邻居。每次从当前单词出发，遍历每个位置修改成a到z的26种可能，这样每个单词最多生成L×26个候选词，也就是最多260个候选，然后在字典里查是否存在。这个每次扩展的成本是O(L×26)，远低于遍历整个字典找邻居的O(N×L)。
这里有一个非常关键的实现细节：字典的查找数据结构。Python里用set存wordList，查询是O(1)平均复杂度；如果用list，查询是O(N)，整体复杂度直接退化到不可接受。Java里则用HashSet。这是整个算法性能的基石，很多第一次写这道题的人在这里吃了大亏，用列表存字典导致提交超时。
2.2 标准BFS的完整实现细节
我用Java写一版标准BFS的实现，因为Java在这类搜索题里的代码可读性比较好，面试中也更常用。
class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { // 用HashSet存字典，O(1)的查询效率 Set<String> dict = new HashSet<>(wordList); // 如果终点不在字典里，直接返回0 if (!dict.contains(endWord)) { return 0; } // 用队列做BFS，起始单词作为起点 Queue<String> queue = new LinkedList<>(); queue.offer(beginWord); // 记录已访问的单词，避免走回头路形成死循环 Set<String> visited = new HashSet<>(); visited.add(beginWord); // 步数从1开始，因为beginWord自身算一层 int step = 1; while (!queue.isEmpty()) { int size = queue.size(); // 每次处理一整层 for (int i = 0; i < size; i++) { String cur = queue.poll(); // 如果当前单词和目标单词相同，说明找到最短路径 if (cur.equals(endWord)) { return step; } // 枚举所有可能的下一层单词 char[] arr = cur.toCharArray(); for (int j = 0; j < arr.length; j++) { char original = arr[j]; for (char c = 'a'; c <= 'z'; c++) { if (c == original) { continue; } arr[j] = c; String next = new String(arr); // 在字典里 && 没访问过 if (dict.contains(next) && !visited.contains(next)) { queue.offer(next); visited.add(next); } } arr[j] = original; } } step++; } return 0; } }这段代码有几点需要特别留意。
step为什么从1开始而不是从0开始？因为题目要求的是“转换序列中单词的个数”，包括起始词和结束词。比如beginWord = "hit"、endWord = "cog"，最短路径是hit -> hot -> dot -> dog -> cog，长度是5。层序遍历时，第一层是hit本身，此时step = 1；第二层是只改一个字母能到达的单词，step = 2；当BFS到达cog那一层时，step恰好等于从起点到终点的节点数。从0开始会导致结果差1，这是这道题最容易错的地方。
visited集合的加入时机也值得说。标准BFS有两种做法：一种是在出队时判断是否访问过，另一种是在入队时立刻标记visited。这里采用了后者，因为同一个单词如果通过多条路径到达，入队时标记可以避免它被重复加入队列多次。如果等到出队时才标记，hit -> hot和hit -> lot可能在某一层产生同一个单词入队两次，队列里会出现重复节点，虽然最终结果可能不受影响，但时间复杂度和内存消耗都会变大，极端情况下会超时。
在修改字符时，遍历完一个分支后需要arr[j] = original恢复原字符。这里我找了一个很隐蔽的坑：如果不恢复原字符，那么处理下一个位置时会基于已经被修改的字符来继续替换，导致生成的候选词完全错误。比如cur = "hit"，在j=0位置把h改成a得到"ait"，如果不恢复，下一步j=1位置替换的是a位置的字符，而不是原来的i，最终得到的候选词实际从原始字符中丢失了h，导致漏掉很多合法路径。这个细节非常容易忽略，我在调试时遇到过一两次，定位到原因后直拍大腿。
2.3 时间复杂度与空间复杂度的直观理解
标准BFS的时间复杂度是O(N·L²·26)。为什么是N·L²而不是N·L·26？因为每次生成候选词都要调用new String(arr)，这一步本身就是O(L)的耗时。最坏情况下每个单词都要从队列出队一次，生成L×26个候选词，每个候选词还要做字符串构造和HashSet查询，所以总复杂度是O(N·L·26·L) = O(N·L²·26)。在N=5000、L=10时，这个量级大约在千万级别，是可以在几百毫秒内跑完的。
空间复杂度是O(N·L)，主要是队列和visited集合存储单词所占的空间。这个空间占用在题目约束下完全可控，不需要额外担心。
3. 解法二：双向BFS的加速原理与实现
3.1 为什么双向BFS能快这么多？指数缩减的核心逻辑
标准BFS是从起点单向向外扩张，每一层能到达的节点数按分支因子指数增长。假设每个节点平均有K个邻接节点，那么单向BFS要搜索到第D层才找到终点，访问的总节点数大约是1 + K + K² + ... + K^D，也就是O(K^D)量级。
双向BFS的思路是从起点和终点同时向外扩张，每次选择当前规模较小的一侧先扩展一层。当两侧的访问区域相遇时，最短路径就找到了。如果最短路程是D，那么每一侧只需要扩展大约D/2层，访问的节点总数是2 × (1 + K + K² + ... + K^(D/2))，也就是O(K^(D/2))量级。这个差异是巨大的：如果K=26、D=10，单向BFS要访问约26¹⁰个节点（虽然实际被字典限制远到不了这么多），双向BFS每侧只访问约26⁵个节点，差距是指数级别的。在实际的测试数据里，双向BFS通常比标准BFS快3到8倍，有些场景下甚至快一个数量级。
这个原理其实和日常生活中的碰头逻辑很相似：两个人分别从家和公司出发，在中间某个地点碰头，显然比一个人从头跑到尾快得多，前提是双方都知道对方的目标位置。
3.2 双向BFS的实现细节与坑点
双向BFS的实现比标准BFS多了一个Set作为另一侧的访问集合，核心机制是：每次从节点数较少的一侧向外扩展一层，然后检查扩展出的新节点是否出现在另一侧的集合中，如果出现就说明两侧“接上头”了，路径长度等于步数之和。
我写一版Python实现，因为在双向BFS的场景里，Python的set操作非常方便，代码也简洁，利于理解逻辑：
def ladderLength(beginWord, endWord, wordList): wordSet = set(wordList) if endWord not in wordSet: return 0 # 两侧的访问集合，同时作为BFS的“队列” beginSet = {beginWord} endSet = {endWord} visited = set() visited.add(beginWord) visited.add(endWord) step = 1 L = len(beginWord) while beginSet and endSet: # 每次从较小的一侧扩展，大幅减少搜索空间 if len(beginSet) > len(endSet): beginSet, endSet = endSet, beginSet nextSet = set() for word in beginSet: arr = list(word) for i in range(L): original = arr[i] for c in 'abcdefghijklmnopqrstuvwxyz': if c == original: continue arr[i] = c newWord = ''.join(arr) if newWord in endSet: return step + 1 if newWord in wordSet and newWord not in visited: nextSet.add(newWord) visited.add(newWord) arr[i] = original beginSet = nextSet step += 1 return 0这段代码里有个非常重要的语义转换：step的含义不再是单一BFS的“层数”，而是两侧扩展的总步数。具体来说，step初始为1，表示起始层。在每轮循环中，从beginSet向外扩展一层，如果扩展出来的单词能命中endSet，说明从起点到终点一共走了step + 1步（当前这一侧多走了一步），所以直接返回step + 1。
有一个我实测踩过的坑：visited集合的维护时机。这里在把新单词加入nextSet时就同步加入visited，目的是防止同一层内出现重复节点，也防止两个方向各自回头路。如果不加visited，在单词数量较多时会产生大量无效扩展，最坏情况下双向BFS退化成暴力BFS，加速效果大打折扣。
还有一个容易被忽略的点：两侧集合的交替扩展。代码里通过if len(beginSet) > len(endSet)交换两个集合，确保每次都是较小的一侧先扩展。这个“贪心”策略在工程上效果极好，因为小集合扩展后的新集合往往不会比大集合大太多，既保证了正确性又控制了规模。理论上如果不交换也可以，但实测下来在一些特殊数据上性能会差很多，尤其是当其中一侧的集合膨胀特别快的时候。
3.3 双向BFS的边界情况处理
双向BFS有一些容易出错的边界场景，这里单独提出来说明。
场景一：beginWord和endWord相同。题目没有明确排除这种情况，但实际上不会出现，因为字典里的单词应该都和beginWord不同。如果真的相等，标准BFS会在第一层就命中，双向BFS也会在初始化时发现beginSet和endSet有交集，此时需要在循环开始前加一个特判。稳妥起见，很多解法在开头就加入if beginWord.equals(endWord) return 1，虽然这通常不触发，但增加安全性。
场景二：endWord不在字典中。这一点一定不能漏，因为题目说得很清楚，结束词必须在字典里才可能有解。如果endWord不在wordList中，直接返回0。我在第一次写的时候漏了这个判断，结果一个测试用例返回了1，因为队列里先弹出了endWord碰巧和起点相同，而真正应该返回的是0，这种边缘错误定位起来很费劲。
场景三：无法接龙的情况。标准BFS的队列会清空，返回0；双向BFS会有一侧集合先变空，循环退出，返回0。这两种循环退出条件设置好后就互相同步了。
4. 两种解法对比与选型建议
| 维度 | 标准BFS | 双向BFS |
|---|---|---|
| 实现难度 | 简单，属于BFS模板题 | 中等，需要维护两个集合和边界判断 |
| 时间复杂度 | O(N·L²·26) | O(N·L²·26)的理论上界不变，但实际搜索空间大幅缩小 |
| 空间占用 | O(N·L) | O(N·L)的2倍以内，因为多了另一侧的集合 |
| 适用场景 | 代码量优先、逻辑要讲清楚 | 追求性能、对耗时敏感的场合 |
| 典型耗时（N=5000,L=10） | 约150ms~300ms | 约30ms~100ms |
| 面试讲解复杂度 | 逻辑清晰，适合讲清BFS思想 | 需要额外说明“为什么双向更快” |
实际场景中该怎么选？我个人的建议是：如果你是在面试中遇到这道题，先写出标准BFS并讲清楚原理，这是在考察BFS基本功。如果面试官追问“能不能更快”，再展示双向BFS的优化思路。如果你是在刷LeetCode热门100题，用双向BFS一版直接提交，性能和代码量都比较理想。
还有一种更进阶的做法是“逐字母替换+字典预处理”，即把所有单词按位置分组，构建通配符映射（如h*t映射到hot），然后在BFS时基于通配符直接找到邻居，不需要每轮枚举26个字母。这种做法的预计算时间是O(N·L)，但BFS每次扩展只需要查询哈希表，速度会更快。不过实现复杂度略高，而且在面试中容易把简单问题复杂化，一般不建议作为首要方案。
5. 常见问题与避坑指南
5.1 为什么我的BFS超时了？
最可能的原因是字典查询用了List而不是Set。在Python里是list而不是set，在Java里是ArrayList而不是HashSet。字符串逐个比较的时间开销在数据量大时完全是灾难级别的。把字典转成哈希集合后，整体性能立刻改观。
另一个常见原因是visited集合没加或加晚了。重复入队会导致队列膨胀，每一层的节点数翻倍，最终复杂度指数上升。可以做一个简单实验：把visited的标记从入队时移到出队时，观察一下运行时间的变化，差距会非常明显。
5.2 为什么双向BFS的结果比标准BFS少1？
这个坑我已经在上面详细说过了：双向BFS的step初始化值和扩展逻辑要仔细核对。双向BFS每次从一侧扩展一层，只有当新扩展的单词命中另一侧时才算接上了头，此时返回的应该是“当前已走过的步数 + 这一层的1步”。如果初始化step = 0，返回值就是step + 2而不是step + 1，要对号入座，不能死套模板。
5.3 单词里的重复字符会不会影响正确性？
不会。代码里对每个位置枚举26个字母时会跳过和原字符相同的候选，但这只是跳过重复候选，不影响正确性。比如"hot"中第一个位置改成'h'得到"hot"，和原词相同，跳过即可；但第二个位置改成'o'得到"hot"，同样跳过。真正影响的是重复候选导致重复入队，但这已被visited拦截了。
5.4 字典中单词长度不一致怎么办？
题目保证所有单词长度相同，不需要特殊处理。但在实际工程中如果遇到变长度单词，每个单词需要按自身长度来枚举候选，不能在同一个循环里统一处理不同长度的单词。
6. 从这道题延伸出去的经典变体
单词接龙这道题的思维框架可以迁移到很多其他问题上。LeetCode 126是这道题的变体，要求输出“所有最短路径”，需要记录前驱节点，本质上是在BFS树上做回溯，复杂度会比127高不少。LeetCode 433“最小基因变化”几乎就是单词接龙的换皮版本，把字典换成了基因序列库，规则从改一个字母变成改一个字符。还有LeetCode 752“打开转盘锁”，也是BFS+剪枝的套路，锁和字典对应，改一个数字对应改一个字母。
如果你在刷LeetCode周赛，这类BFS题几乎是必考题型。近期的周赛430里就有一道类似的“最短路程”题，用的就是BFS+状态压缩的组合。所以把单词接龙彻底吃透，不仅仅是为了这一道题，BFS的模板思想是可以反复套用的。
我在刷题过程中最大的感悟是：这种经典搜索题，不要光看题解，一定要自己动手写，尤其是双向BFS的边界处理，只有亲手踩过坑、调试过错误结果，才能真正理解为什么要在入队时标记visited、为什么返回的是step + 1而不是step。把这些细节想明白之后，遇到任何BFS变体都能举一反三。
