LeetCode-Go 题解：127. Word Ladder 单词接龙 BFS 最短转换序列

LeetCode-Go 题解：127. Word Ladder 单词接龙 BFS 最短转换序列

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文基于开源仓库 LeetCode-Go（README.md）中 0127.Word-Ladder 的题解文档，完整讲解 LeetCode 第 127 题「Word Ladder（单词接龙）」：如何用广度优先搜索（BFS）在给定字典中找到从beginWord到endWord的最短转换序列长度。你将掌握该题 BFS 分层遍历的核心思路、Go 语言实现细节、候选词生成技巧、复杂度分析，并通过仓库内的单元测试用例验证算法正确性。本题与 126. Word Ladder II（找出全部最短路径）是姊妹题，是图论 BFS 与字符串处理的经典组合题型。

题目描述

给定两个单词beginWord和endWord，以及一个字典wordList，找出从beginWord变换到endWord的最短转换序列的长度。转换需满足如下两条规则：

1. 每次转换只能改变一个字母。
2. 转换过程中的每个中间单词都必须是字典wordList中的单词。

注意：beginWord本身不是转换产物，即它不要求出现在wordList中。

题目约束（Note）

• 如果不存在这样的转换序列，返回0。
• 所有单词具有相同的长度。
• 所有单词只由小写字母组成。
• 字典中不存在重复的单词。
• beginWord和endWord非空，且二者不相同。

示例一

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: 一条最短转换序列为 "hit" -> "hot" -> "dot" -> "dog" -> "cog"， 返回其长度 5。

示例二

Input: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] Output: 0 Explanation: endWord "cog" 不在 wordList 中，因此不存在可行的转换序列。

解题思路：BFS 分层求最短路径

题目虽然要求输出「最短」转换序列的长度，但实际上最短路径的寻找方式已经被题目的两条规则固定了：

1. 每次只变换一个字母；
2. 每次变换后的单词都必须在wordList中。

因此不需要额外设计「哪一种变换方式更短」的启发式策略，直接用BFS（广度优先搜索）逐层扩散即可，BFS 首次到达endWord时的层数就是最短长度。可以这样理解：把所有单词看作图的顶点，两个单词若只差一个字母则存在一条无向边，本题本质上是求无权图上从beginWord到endWord的最短路径长度。

BFS 执行流程

• 从beginWord开始变换：把当前单词的每个字母位置依次用'a' ~ 'z'替换一遍，生成全部候选词；
• 生成的候选词到wordList中查找是否命中，这里用Map（哈希表）记录字典，实现 O(1) 查找；
• 命中且尚未访问过（未出队过）的单词入队，并立即从 Map 中删除（相当于 visited 标记，防止回头访问造成死循环）；
• 每遍历完一层，深度depth加 1；
• 当某个候选词恰好等于endWord时，返回当前层数 + 1；
• 当队列为空（len(queue) <= 0，所有可达单词都已出队）仍未找到endWord，整个程序结束，返回 0。

这里用「入队即从 Map 删除」来替代单独的 visited 数组，是一处非常典型的空间优化技巧：因为 BFS 中先到达某单词的路径必然最短，一旦入队就无需再次入队，直接删除即可，既避免了重复扩展，又省去了 visited 标记结构。

Go 源码实现与逐段剖析

仓库中的核心实现在 127. Word Ladder.go，完整代码如下：

package leetcode func ladderLength(beginWord string, endWord string, wordList []string) int { wordMap, que, depth := getWordMap(wordList, beginWord), []string{beginWord}, 0 for len(que) > 0 { depth++ qlen := len(que) for i := 0; i < qlen; i++ { word := que[0] que = que[1:] candidates := getCandidates(word) for _, candidate := range candidates { if _, ok := wordMap[candidate]; ok { if candidate == endWord { return depth + 1 } delete(wordMap, candidate) que = append(que, candidate) } } } } return 0 } func getWordMap(wordList []string, beginWord string) map[string]int { wordMap := make(map[string]int) for i, word := range wordList { if _, ok := wordMap[word]; !ok { if word != beginWord { wordMap[word] = i } } } return wordMap } func getCandidates(word string) []string { var res []string for i := 0; i < 26; i++ { for j := 0; j < len(word); j++ { if word[j] != byte(int('a')+i) { res = append(res, word[:j]+string(rune(int('a')+i))+word[j+1:]) } } } return res }

主函数ladderLength

• 第一行一次性完成三件事：用getWordMap把wordList转成哈希表wordMap；初始化 BFS 队列que，起点为beginWord；初始化深度depth为 0。
• 外层for len(que) > 0是 BFS 的层循环，进入每层前depth++表示「又走了一步」。
• 内层for i := 0; i < qlen; i++固定当前层的长度qlen再遍历，这是分层 BFS 的关键写法：保证同一深度depth的所有单词在本轮全部扩展完，下一轮才进入depth+1，从而保证返回的一定是最短层数。
• 每个单词出队后调用getCandidates生成所有「只差一个字母」的候选词。
• 对每个候选词做 Map 命中判断：
  • 命中wordMap说明候选词是字典中的合法单词且尚未访问；
  • 若候选词就是endWord，直接返回depth + 1（depth是起点到当前单词的步数，再加一步到达终点）；
  • 否则delete(wordMap, candidate)标记已访问，并入队，等待下一层扩展。
• 队列清空仍未命中endWord，说明字典无法连通终点，返回0。

辅助函数getWordMap：字典预处理

• 将wordList转成map[string]int，value 记录单词在字典中的下标（本题只用 key 做存在性判断）。
• 双重去重：外层去重针对字典本身可能出现的重复单词（题目已保证无重复，此处是防御性写法）；内层显式跳过beginWord——因为beginWord不是「转换产物」，且它作为起点早已入队，若再放入 Map 会导致后续绕回起点。

辅助函数getCandidates：候选词生成

• 双重循环枚举：外层i遍历'a' ~ 'z'共 26 个字母，内层j遍历单词的每个下标位置。
• 当目标位置j的字符与待替换字母不同时，用word[:j] + 新字母 + word[j+1:]拼接出候选词（word[j] != byte(int('a')+i)的判断避免了生成与自身相同的「无效候选词」）。
• 对长度为L的单词，每个单词恰好生成26 * L（实际25 * L左右，剔除自身）个候选词。

单元测试与验证

仓库为本题配套了表驱动测试用例，见 127. Word Ladder_test.go：

type question127 struct { para127 ans127 } type para127 struct { b string e string w []string } type ans127 struct { one int } func Test_Problem127(t *testing.T) { qs := []question127{ { para127{"hit", "cog", []string{"hot", "dot", "dog", "lot", "log", "cog"}}, ans127{5}, }, { para127{"hit", "cog", []string{"hot", "dot", "dog", "lot", "log"}}, ans127{0}, }, } ... }

两个用例与题目给出的示例一一对应：

可以用 Go 内置测试框架在仓库根目录运行该用例：

cd leetcode/0127.Word-Ladder go test -v -run Test_Problem127

该测试同时验证了「找到终点返回步数」与「找不到终点返回 0」两条关键分支，覆盖了 BFS 的两类退出条件。

复杂度分析

• 时间复杂度：对每个入队单词，getCandidates都要生成26 × L个候选词，每个候选词的拼接开销为 O(L)；每个字典单词最多入队一次，因此整体为O(26 × L × N)（其中 N 为字典中可达单词数量，L 为单词长度），即O(N × L²)量级。
• 空间复杂度：wordMap存储整个字典为 O(N)；BFS 队列最坏情况下容纳一层内的所有单词为 O(N)，总体为O(N)。

仓库 website/content/ChapterTwo/Breadth_First_Search.md 的 BFS 专题列表中同样记录了本题的复杂度标注：时间 O(n)、空间 O(n)（n 为字典规模）。

与姊妹题 126. Word Ladder II 的关联

本题只要求返回最短序列的长度，而 0126.Word-Ladder-II 要求找出全部最短转换序列（返回列表而非长度）。二者的图模型与 BFS 骨架完全一致；区别在于：

• 127 题只需要记录层数，到达终点即可提前返回；
• 126 题需要在 BFS 的同时记录每一层的前驱关系（或先 BFS 建图再 DFS 回溯），才能枚举出所有等长最短路径。

因此 127 题是 126 题的简化版本，掌握了本题的分层 BFS 写法，再进一步理解前驱链重建，即可顺藤摸瓜攻克 126 题。

小结

Word Ladder 是 BFS 求无权图最短路径的经典考题，核心要点可以归纳为三点：

1. 建图隐式化：不显式构建单词图，而是每次动态生成 26 × L 个候选词并用哈希表 O(1) 判断合法性；
2. 分层 BFS 计数：用「固定qlen的内层循环」保证按层推进，depth累加即得路径长度；
3. 入队即删除：用删除 Map 元素代替 visited 数组，天然防止回头与重复扩展。

结合仓库源码（127. Word Ladder.go）与测试（127. Word Ladder_test.go）研读，这套「分层 BFS + 哈希去重 + 候选词生成」的组合打法，同样适用于 433. Minimum Genetic Mutation 等一批「单词/状态逐位变换求最短路」的题目。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go