第8章｜图与并查集
Unit 09 · LeetCode #127 单词接龙
仅本次页面有效
U09
Implicit Graph BFSGenerate Neighbor → Enqueue Once → Expand by Layer → First Hit Is Shortest
图的边不一定预先写出来，
也可以在搜索时即时生成。
把每个单词视为节点；两个单词只差一个字符时存在边。BFS 按转换步数分层扩展，第一次到达 endWord 时得到最短转换序列。关键不是枚举全部单词对，而是对当前单词逐位置替换字符，只保留仍在候选集合中的新单词。
检测到上次学习现场阶段、案例、BFS 层、候选词、代码槽位和迁移进度均可恢复。
LeetCode #127 · 单词接龙
给定两个单词 beginWord、endWord 和字典 wordList。一次转换只能改变一个字母，且转换后的每个中间单词必须存在于字典中。返回从起始单词到目标单词的最短转换序列所包含的单词数量；不存在转换序列时返回 0。
示例 1
输入：beginWord = "hit", endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：hit → hot → dot → dog → cog
示例 2
输入：beginWord = "hit", endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出：0
约束与 Python 签名
1 ≤ beginWord.length ≤ 10
endWord.length == beginWord.length
1 ≤ wordList.length ≤ 5000
wordList[i].length == beginWord.length
单词仅由小写英文字母组成
wordList 中单词互不相同
beginWord != endWord
class Solution:
def ladderLength(self, beginWord, endWord, wordList):
...
本实验采用单向 BFS。队列中的长度表示“从 beginWord 到当前单词的序列单词数”。
Implicit Graph
节点显式给出，但边不预建；访问当前节点时根据规则生成邻居。
One-Letter Neighbor
长度相同且恰好一个位置字符不同，才构成一条无权边。
BFS Layer
同一层中的单词具有相同最短序列长度；下一层统一加一。
Mark on Enqueue
单词第一次入队时立即从候选集合删除，避免重复入队。
隐式图 BFS步骤 1