题目描述
思路解析动画文字版
关键不是背模板，而是看懂为什么这题适合图 · BFS。
1. BFS 起点 hit 出队，距离=1：BFS 从 hit 出发，距离记 1。每次把当前单词「改一位字母」，若新词在词表里就是它的邻居。
2. 枚举 hit 改一位 → 找到邻居 hot：h_t→hot、_it/hi_ 都不在词表，只有 hot 命中 → hot 是 hit 的邻居。
3. hot 入队，距离=2：hot 入队、距离 2。BFS 逐层扩展，第一次到某词时的距离一定最短。
4. 扩展 hot → dot、lot 同层入队(距离=3)：hot 改一位得 dot、lot(都在词表)→ 同一层一起入队，距离 3。
5. 扩展 dot/lot → dog、log(距离=4)：dot→dog、lot→log，第 4 层入队，距离 4。
6. dog、log 都能改一位到 cog(距离=5)：dog 和 log 各改一位都能到 cog → cog 距离 5。
7. 第一次到 cog → 距离 5 就是最短：BFS 按层推进、距离从小到大，第一次碰到 cog 的距离 5 就是答案(最短变换序列的单词数)。
8. 为什么 BFS 第一次到达即最短？：BFS 是一圈圈向外扩：先访问距离 1 的、再距离 2…… 同一距离的节点一起处理。所以任何节点「第一次被访问」时的距离必然是它的最短距离，无需再更新。
把这句话记住，下次遇到同类题，就能更快选出方向。
边界三连：边界三连：极端输入先过一遍。
几个高频追问，记住答法。
参考代码
from collections import dequeclass Solution: def ladderLength(self, beginWord, endWord, wordList): words = set(wordList) if endWord not in words: return 0 q = deque([(beginWord, 1)]) seen = {beginWord} while q: word, dist = q.popleft() if word == endWord: return dist for i in range(len(word)): for c in "abcdefghijklmnopqrstuvwxyz": nxt = word[:i] + c + word[i+1:] # 改第 i 位 if nxt in words and nxt not in seen: seen.add(nxt) q.append((nxt, dist + 1)) return 0复杂度
- 时间复杂度：O(N·L²·26)，N 词×L 位×26 字母,每次构造新词再花 O(L)
- 空间复杂度：O(N·L)，队列与 seen 存最多 N 个词、每词 L 字符
可套用的代码模板
模板不是死背，而是提醒你写代码前先把状态、转移和边界排好。
Python
# 图 · BFS 通用检查表# 1. 定义状态/指针/容器# 2. 每轮只做一个清晰动作# 3. 更新答案并处理边界易错点
面试追问把动画讲成自己的话
追问为什么用 BFS 而不是 DFS？
追问怎么优化？
追问复杂度？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
除法求值
LeetCode 399 · 中等 · 沿着 图 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题