单词接龙

怎样从“beginWord="hit",endWord="cog",词列表变图,最短变换序列长度。”推导出 图 BFS · 单词接龙，并证明每次状态变化都不会漏掉答案？

中心结论：单词为结点,差一字母有边;BFS 层即最短序列长度(含起点)。

给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

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

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

在本站主例中，beginWord="hit",endWord="cog",词列表变图,最短变换序列长度。

算法最终需要得到或观察：hit→hot→dot→dog→cog 序列长度 5(非 4 次变化)。

重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“图搜索前线”，明确答案需要观察什么。
2. 2状态只维护 queue、visited、level、wordSet。
3. 3转移每一步按照 单词为结点,差一字母有边;BFS 层即最短序列长度(含起点)。
4. 4收尾读取 hit→hot→dot→dog→cog 序列长度 5(非 4 次变化)。，并复核边界与复杂度。

先把题目对象翻译成节点和边，再选择 BFS 或 DFS。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：queue、visited、level、wordSet。

这一题要求输出从 `beginWord` 变换到 `endWord` 最短变换次数。可以用 BFS，从 `beginWord` 开始变换，把该单词的每个字母都用 `'a'~'z'` 变换一次，生成的数组到 `wordList` 中查找，这里用 Map 来记录查找。找得到就入队列，找不到就输出 0 。入队以后按照 BFS 的算法依次遍历完，当所有单词都 `len(queue)<=0` 出队以后，整个程序结束。 这一题题目中虽然说了要求找到一条最短的路径，但是实际上最短的路径的寻找方法已经告诉你了： 1. 每次只变换一个字母 2. 每次变换都必须在 `wordList` 中 所以不需要单独考虑何种方式是最短的。

单词为结点,差一字母有边;BFS 层即最短序列长度(含起点)。

执行过程中持续维护：queue、visited、level、wordSet。

正确性依赖以下不变量：隐形无权图:BFS 首次到达 endWord 时 level 即最短序列长度。；visited 入队时标记;size 冻结当前层。

面试时可以压缩为：wordSet+变字母 BFS:时间 O(N·L²) 空间 O(N);通配符桶空间 O(N·L)。N=词数,L=词长。

落到当前题，执行机制可以压缩为：单词为结点,差一字母有边;BFS 层即最短序列长度(含起点)。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入beginWord="hit",endWord="cog",词列表变图,最短变换序列长度。 因为：单词为结点,差一字母有边;BFS 层即最短序列长度(含起点)。
2. 2BFS 按层扩展单词起点入队。 因为：BFS 保证最短变换序列。
3. 3扩展 'hot' 的邻词尝试每个位置的 26 字母。 因为：dict 中存在且未访问则入队。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5扩展 'lot' 的邻词尝试每个位置的 26 字母。 因为：dict 中存在且未访问则入队。
6. 6扩展 'dog' 的邻词尝试每个位置的 26 字母。 因为：dict 中存在且未访问则入队。
7. 7命中 'cog',长度 5BFS 首次到达即最短。 因为：按层扩展。
8. 8收尾与复杂度hit→hot→dot→dog→cog 序列长度 5(非 4 次变化)。 因为：时间 O(N·L²) · 空间 O(N)。单词为结点,差一字母有边;BFS 层即最短序列长度(含起点)。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

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
}

func main() {
    // 1. 主例
    //    输入：mode="word-ladder", beginWord="hit", endWord="cog", wordList=["hot","dot","dog","lot","log","cog"]
    //    期望：hit→hot→dot→dog→cog 序列长度 5(非 4 次变化)。
    //
    // 2. 失败 / 未命中
    //    检查：答案写成变化次数 4 而非序列长度 5。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC752 转盘锁；LC126 双向
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意beginWord="hit",endWord="cog",词列表变图,最短变换序列长度。
2. 2重复重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。
3. 3优化单词为结点,差一字母有边;BFS 层即最短序列长度(含起点)。
4. 4证明隐形无权图:BFS 首次到达 endWord 时 level 即最短序列长度。；visited 入队时标记;size 冻结当前层。
5. 5复杂度时间 O(N·L²)，空间 O(N)