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-GoREADME.md中 0127.Word-Ladder 的题解文档完整讲解 LeetCode 第 127 题「Word Ladder单词接龙」如何用广度优先搜索BFS在给定字典中找到从beginWord到endWord的最短转换序列长度。你将掌握该题 BFS 分层遍历的核心思路、Go 语言实现细节、候选词生成技巧、复杂度分析并通过仓库内的单元测试用例验证算法正确性。本题与 126. Word Ladder II找出全部最短路径是姊妹题是图论 BFS 与字符串处理的经典组合题型。题目描述给定两个单词beginWord和endWord以及一个字典wordList找出从beginWord变换到endWord的最短转换序列的长度。转换需满足如下两条规则每次转换只能改变一个字母。转换过程中的每个中间单词都必须是字典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 分层求最短路径题目虽然要求输出「最短」转换序列的长度但实际上最短路径的寻找方式已经被题目的两条规则固定了每次只变换一个字母每次变换后的单词都必须在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[j1:]) } } } 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的所有单词在本轮全部扩展完下一轮才进入depth1从而保证返回的一定是最短层数。每个单词出队后调用getCandidates生成所有「只差一个字母」的候选词。对每个候选词做 Map 命中判断命中wordMap说明候选词是字典中的合法单词且尚未访问若候选词就是endWord直接返回depth 1depth是起点到当前单词的步数再加一步到达终点否则delete(wordMap, candidate)标记已访问并入队等待下一层扩展。队列清空仍未命中endWord说明字典无法连通终点返回0。辅助函数getWordMap字典预处理将wordList转成map[string]intvalue 记录单词在字典中的下标本题只用 key 做存在性判断。双重去重外层去重针对字典本身可能出现的重复单词题目已保证无重复此处是防御性写法内层显式跳过beginWord——因为beginWord不是「转换产物」且它作为起点早已入队若再放入 Map 会导致后续绕回起点。辅助函数getCandidates候选词生成双重循环枚举外层i遍历a ~ z共 26 个字母内层j遍历单词的每个下标位置。当目标位置j的字符与待替换字母不同时用word[:j] 新字母 word[j1:]拼接出候选词word[j] ! byte(int(a)i)的判断避免了生成与自身相同的「无效候选词」。对长度为L的单词每个单词恰好生成26 * L实际25 * L左右剔除自身个候选词。单元测试与验证仓库为本题配套了表驱动测试用例见 127. Word Ladder_test.gotype 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}, }, } ... }两个用例与题目给出的示例一一对应输入期望输出说明(hit, cog, [hot,dot,dog,lot,log,cog])5存在最短路径hit - hot - dot - dog - cog(hit, cog, [hot,dot,dog,lot,log])0endWord不在字典中无可达路径可以用 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 求无权图最短路径的经典考题核心要点可以归纳为三点建图隐式化不显式构建单词图而是每次动态生成 26 × L 个候选词并用哈希表 O(1) 判断合法性分层 BFS 计数用「固定qlen的内层循环」保证按层推进depth累加即得路径长度入队即删除用删除 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 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-GoREADME.md中 0127.Word-Ladder 的题解文档完整讲解 LeetCode 第 127 题「Word Ladder单词接龙」如何用广度优先搜索BFS在给定字典中找到从beginWord到endWord的最短转换序列长度。你将掌握该题 BFS 分层遍历的核心思路、Go 语言实现细节、候选词生成技巧、复杂度分析并通过仓库内的单元测试用例验证算法正确性。本题与 126. Word Ladder II找出全部最短路径是姊妹题是图论 BFS 与字符串处理的经典组合题型。题目描述给定两个单词beginWord和endWord以及一个字典wordList找出从beginWord变换到endWord的最短转换序列的长度。转换需满足如下两条规则每次转换只能改变一个字母。转换过程中的每个中间单词都必须是字典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 分层求最短路径题目虽然要求输出「最短」转换序列的长度但实际上最短路径的寻找方式已经被题目的两条规则固定了每次只变换一个字母每次变换后的单词都必须在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[j1:]) } } } 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的所有单词在本轮全部扩展完下一轮才进入depth1从而保证返回的一定是最短层数。每个单词出队后调用getCandidates生成所有「只差一个字母」的候选词。对每个候选词做 Map 命中判断命中wordMap说明候选词是字典中的合法单词且尚未访问若候选词就是endWord直接返回depth 1depth是起点到当前单词的步数再加一步到达终点否则delete(wordMap, candidate)标记已访问并入队等待下一层扩展。队列清空仍未命中endWord说明字典无法连通终点返回0。辅助函数getWordMap字典预处理将wordList转成map[string]intvalue 记录单词在字典中的下标本题只用 key 做存在性判断。双重去重外层去重针对字典本身可能出现的重复单词题目已保证无重复此处是防御性写法内层显式跳过beginWord——因为beginWord不是「转换产物」且它作为起点早已入队若再放入 Map 会导致后续绕回起点。辅助函数getCandidates候选词生成双重循环枚举外层i遍历a ~ z共 26 个字母内层j遍历单词的每个下标位置。当目标位置j的字符与待替换字母不同时用word[:j] 新字母 word[j1:]拼接出候选词word[j] ! byte(int(a)i)的判断避免了生成与自身相同的「无效候选词」。对长度为L的单词每个单词恰好生成26 * L实际25 * L左右剔除自身个候选词。单元测试与验证仓库为本题配套了表驱动测试用例见 127. Word Ladder_test.gotype 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}, }, } ... }两个用例与题目给出的示例一一对应输入期望输出说明(hit, cog, [hot,dot,dog,lot,log,cog])5存在最短路径hit - hot - dot - dog - cog(hit, cog, [hot,dot,dog,lot,log])0endWord不在字典中无可达路径可以用 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 求无权图最短路径的经典考题核心要点可以归纳为三点建图隐式化不显式构建单词图而是每次动态生成 26 × L 个候选词并用哈希表 O(1) 判断合法性分层 BFS 计数用「固定qlen的内层循环」保证按层推进depth累加即得路径长度入队即删除用删除 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考