LeetCode LCR 108. 单词接龙
目录
题目描述
题意分析
给起始单词
beginWord、目标单词endWord和一个词典wordList。每次只能改变单词中的一个字母，且改完之后得到的单词必须在词典里。问从beginWord变到endWord最短需要经过多少个单词（包含首尾两端），无法转换则返回 0。「每次改一个字母」定义了单词之间的相邻关系，「最短」说明这是最短路问题。把每个单词看成一个节点、把「相差恰好一个字母」看成一条权为 1 的边，题目就是求
beginWord到endWord的最短路径长度。边权全为 1，所以 BFS 就够，不需要任何带权最短路算法。有两处细节必须从题面里抠出来。第一，返回的是单词个数而不是变换次数，两者差 1；
beginWord自身要算进去。第二，beginWord不一定在wordList里，但endWord必须在，否则无解——因为每一步变换后的单词都必须落在词典中。约束里单词长度
L ≤ 10、词典规模N ≤ 5000、全为小写字母。这组数字给出了很强的暗示：直接两两比较建图是 $O(N^2 L)$，约 $2.5 \times 10^8$，偏危险；而对一个单词枚举「每个位置换成 26 个字母」只需 $O(26L)$，共 $O(26LN)$，约 $1.3 \times 10^6$，快两个数量级。邻居靠现场生成而不是预先建图，是这道题的关键取舍。边界：
endWord不在词典中时应返回 0；beginWord与endWord可能只差一个字母，此时答案是 2；词典可能含有与beginWord相同的单词，需要保证它不会被反复访问。
解法：哈希表统计状态
核心思路
暴力做法是从
beginWord出发做深度优先搜索，枚举所有可能的变换序列，记录能到达endWord的最短长度。路径数是指数级的，$N = 5000$ 时完全不可行。瓶颈有两层。其一，DFS 会把同一个单词沿不同路径反复展开，而「从某个单词出发到
endWord的最短距离」与「怎么走到这个单词的」无关；其二，判断「哪些单词与当前单词相差一个字母」如果靠遍历整个词典比对，单次就要 $O(NL)$。第一层瓶颈用 BFS 解决：所有边权都是 1，逐层扩散时，某个单词第一次被访问时所在的层号就是它的最短距离，后续再遇到它只可能更远，可以直接丢弃。
第二层瓶颈用「反向生成邻居」解决：与其在词典里搜索谁和我相邻，不如把当前单词的每个位置依次替换成
a到z，得到 $26L$ 个候选串，再用哈希集合 $O(1)$ 地判断哪些候选真的在词典里。这样邻居枚举的代价与词典规模脱钩。于是不变量可以写成：队列中的单词按到
beginWord的距离非递减排列；任何单词一旦被放进队列，就立刻从词典中删除，此后不会再被任何路径重新访问。用「从词典里删掉」代替单独的visited集合，是本题最省事的去重手法——被删掉的单词要么已经在队列里、要么已经处理完，无论哪种情况再访问都不可能更优。计数上，用
answer记录当前层对应的单词个数，初值为 1（只有beginWord时序列长度就是 1）。每处理完一整层就把answer加一。当在展开某个单词时生成出endWord，说明endWord位于下一层，答案是answer + 1，可以立刻返回，不必等它真正出队。队列耗尽仍未命中
endWord，说明两者不连通（包括endWord根本不在词典里的情况），返回 0。
解题步骤
- 把
wordList装进哈希集合words。为什么必须转成集合：后面要做 $26L$ 次成员查询，列表的线性查找会把复杂度乘上 $N$；集合把单次查询压到 $O(L)$（哈希单词本身的代价）。- 队列初始化为只含
beginWord，answer初始化为 1。为什么answer从 1 开始：题目要求的是序列中的单词个数，beginWord自己就占一个；若从 0 开始，最终结果会整体少 1。- 外层
while循环处理队列，内层用for (int i = q.size(); i > 0; --i)精确处理一整层。为什么要先把层大小固定下来：循环体内会往队列尾部追加下一层的元素，如果直接用q.size()作为动态条件，本层和下一层会混在一起，层号（也就是距离）就失去了意义。- 对出队单词的每个位置
j，先备份原字符，再依次替换成a到z。为什么要备份并在内层结束后还原：chars是复用的字符数组，不还原的话第j位的修改会污染第j+1位之后的枚举，生成出大量与原单词相差两位以上的错误候选。- 对每个候选
t，先判words.contains(t)，不在词典就跳过。为什么这个判断要放在最前面：它一次性挡掉了「不是合法单词」和「已经被访问过（因为访问后就被删除了）」两种情况，把去重和合法性检查合并成了一次查询。- 若
t等于endWord，立刻返回answer + 1。为什么可以提前返回而不入队：t属于下一层，此刻已经确定它的距离；BFS 的层序性保证不存在更短的路径，继续搜索只会得到相同或更差的结果。为什么是answer + 1：answer是当前层的序列长度，endWord比当前层多一个单词。- 否则把
t入队并从words中删除。为什么删除要与入队同时发生：这是 BFS 的入队即标记原则。若等到出队再删，同一层里的多个单词会把同一个候选反复推进队列，队列规模膨胀且做大量无用功。- 一整层处理完后
++answer。为什么加在层末而不是层内：answer的语义是「当前正在处理的这一层对应的序列长度」，只有整层耗尽才推进到下一层。- 循环自然结束时返回 0。为什么：队列空了说明从
beginWord可达的单词已经全部访问完却没碰到endWord，二者不连通。以
beginWord = "hit"、endWord = "cog"、wordList = ["hot","dot","dog","lot","log","cog"]走一遍。初始
words = {hot, dot, dog, lot, log, cog}，队列["hit"]，answer = 1。第 1 层（
answer = 1）：出队"hit"。第 0 位换成a..z得到ait、bit…… 均不在词典；第 1 位换到o时得到"hot"，在词典中且不等于"cog"，入队并从词典删除，此时words = {dot, dog, lot, log, cog}；第 2 位的所有替换都不在词典。层结束，answer变成 2，队列是["hot"]。第 2 层（
answer = 2）：出队"hot"。第 0 位换到d得"dot"、换到l得"lot"，两者都在词典，依次入队并删除；第 1 位换回i得"hit"，"hit"从来不在词典里，被contains挡掉——这说明beginWord不在词典时不需要任何特殊处理。层结束，answer变成 3，队列是["dot","lot"]，words = {dog, log, cog}。第 3 层（
answer = 3）：出队"dot"，第 2 位换到g得"dog"，入队并删除；出队"lot"，第 2 位换到g得"log"，入队并删除。注意"lot"在第 0 位换到d时也会生成"dot"，但"dot"已被删除，contains返回假，自动跳过——这就是「删除即标记」在起作用。层结束，answer变成 4，队列是["dog","log"]，words = {cog}。第 4 层（
answer = 4）：出队"dog"，第 0 位换到c得"cog"，在词典中且等于endWord，立刻返回answer + 1 = 5。结果 5，对应序列
hit → hot → dot → dog → cog，共 5 个单词，与题目样例一致。再看无解用例：
wordList = ["hot","dot","dog","lot","log"]（去掉cog）。BFS 会把五个单词全部访问完，词典清空，队列耗尽，任何候选都通不过contains，最终返回 0。
代码实现
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> words = new HashSet<>(wordList);
Queue<String> q = new LinkedList<>();
q.offer(beginWord);
// answer 表示当前层对应的序列长度，beginWord 自身算一个。
int answer = 1;
while (!q.isEmpty()) {
// 先固定本层大小，避免与下一层混在一起。
for (int i = q.size(); i > 0; --i) {
String s = q.poll();
char[] chars = s.toCharArray();
for (int j = 0; j < chars.length; ++j) {
char ch = chars[j];
for (char k = 'a'; k <= 'z'; ++k) {
chars[j] = k;
String t = new String(chars);
// 不在词典中，或已被访问过（访问后即删除）。
if (!words.contains(t)) {
continue;
}
if (endWord.equals(t)) {
return answer + 1;
}
q.offer(t);
// 入队即标记，防止同一单词被重复展开。
words.remove(t);
}
// 还原本位，避免污染后续位置的枚举。
chars[j] = ch;
}
}
++answer;
}
return 0;
}
}
func ladderLength(beginWord string, endWord string, wordList []string) int {
words := make(map[string]bool)
for _, word := range wordList {
words[word] = true
}
q := []string{beginWord}
// answer 表示当前层对应的序列长度，beginWord 自身算一个。
answer := 1
for len(q) > 0 {
// 先固定本层大小，避免与下一层混在一起。
for i := len(q); i > 0; i-- {
s := q[0]
q = q[1:]
chars := []byte(s)
for j := 0; j < len(chars); j++ {
ch := chars[j]
for k := 'a'; k <= 'z'; k++ {
chars[j] = byte(k)
t := string(chars)
// 不在词典中，或已被访问过（访问后即删除）。
if !words[t] {
continue
}
if t == endWord {
return answer + 1
}
q = append(q, t)
// 入队即标记，防止同一单词被重复展开。
words[t] = false
}
// 还原本位，避免污染后续位置的枚举。
chars[j] = ch
}
}
answer++
}
return 0
}
复杂度分析
- 时间复杂度：$O(N \cdot L^2 \cdot 26)$，其中 $N$ 是词典规模、$L$ 是单词长度。凭什么：每个单词最多入队一次、展开一次；一次展开要枚举 $L$ 个位置各 26 个字母，每个候选都要新建一个长度为 $L$ 的字符串并做哈希，字符串构造与哈希各 $O(L)$。本题 $N \le 5000$、$L \le 10$，总量约 $10^7$。
- 空间复杂度：$O(N \cdot L)$。凭什么：哈希集合存下全部词典单词是 $O(NL)$；队列在最坏情况下可能同时容纳一整层的单词，上界同样是 $O(NL)$；每次展开临时构造的字符数组只有 $O(L)$。
关键点总结
- 「每次改动一点、求最少步数」是隐式图上的 BFS 信号：节点是状态（这里是单词），边是一次合法改动，边权恒为 1，所以 BFS 直接给出最短路。
- 邻居要现场生成而不是预先两两建图。$26L$ 次哈希查询远小于 $N$ 次字符串比对，当词典规模远大于单词长度时这个取舍能差出两个数量级——面试中主动比较这两种建边方式是核心得分点。
- 「访问过就从词典里删掉」比单开
visited集合更省，且把「合法性检查」和「去重」合并成了同一次查询；能解释「为什么删掉不会漏解」（更晚到达只可能更远）比写出代码更重要。- 按层处理时必须先固定
q.size()，这是所有需要层号/步数的 BFS 的通用模板。- 返回值是单词个数而非变换次数，且允许在生成出
endWord的瞬间提前返回answer + 1，不必等它出队——理解这一点就不会在+1上反复试错。- 面试视角：进阶优化是双向 BFS，从两端同时扩散、每次扩展较小的一侧，能把搜索规模从 $b^d$ 降到约 $2b^{d/2}$。被追问优化时给出这条，通常就是这道题的天花板答案。
易错点总结
answer从 0 开始：beginWord = "a"、endWord = "c"、wordList = ["a","b","c"]会返回 1 而正确答案是 2，整条链的长度统一少 1。- 忘记把
wordList转成哈希集合：wordList有 5000 个单词时，每次成员判断都是线性扫描，总复杂度乘上 $N$，直接超时。- 内层不还原
chars[j] = ch：beginWord = "hit"在第 0 位停在z时，第 1 位的枚举会基于"zit"展开，生成的候选与原单词相差两位，得到完全错误的邻接关系。- 用
q.size()作为内层动态条件：wordList = ["hot","dot","dog","lot","log","cog"]时本层与下一层混流，answer不再等于层号，返回的步数偏小或偏大。- 入队但不从词典删除：
beginWord = "hit"、wordList = ["hot","dot","dog","lot","log","cog"]中"dot"会被"hot"和"lot"各推入一次，队列规模指数膨胀，大数据下超时。- 在出队时才删除而不是入队时：同一层内多个单词会把同一候选重复入队，去重形同虚设，问题与上一条相同。
- 忘记检查
endWord是否在词典中：endWord = "cog"而wordList = ["hot","dot"]时，若不依赖contains而是靠字符串相等提前返回，会返回一个根本不存在的路径长度；本实现把相等判断放在contains之后，天然规避了这个陷阱。- 把
endWord判断写在contains之前：endWord = "cog"不在词典时会返回非零值，而正确答案是 0。- 担心
beginWord不在词典而额外特判：beginWord = "hit"、wordList不含"hit"时，主逻辑本来就靠contains挡住了回头路，多余的特判只会增加出错面。- 用
String拼接而非char[]生成候选：每次s.substring(0,j) + k + s.substring(j+1)会产生多次中间字符串，常数放大数倍，在 $10^7$ 量级下足以从通过变成超时。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 127. 单词接龙 | 困难 | 与本题同题，可直接套用同一份代码 |
| 126. 单词接龙 II | 困难 | 要求输出全部最短路径，需在 BFS 分层的同时记录前驱再回溯还原 |
| 433. 最小基因变化 | 中等 | 字符集只有 ACGT 四种、长度固定为 8，返回的是变换次数而非单词个数 |
| 752. 打开转盘锁 | 中等 | 每位只能上下拨动而非任意替换，且存在必须绕开的死亡状态 |
| 773. 滑动谜题 | 困难 | 状态是二维棋盘的序列化字符串，邻居由空格的可交换位置决定 |
| 854. 相似度为 K 的字符串 | 困难 | 邻居靠交换两个字符生成，需要剪枝只交换能立刻归位的字符 |
| 542. 01 矩阵 | 中等 | 多源 BFS，源点有多个且状态是网格坐标，可对照隐式图与显式网格的差异 |
| LCR 109. 打开转盘锁 | 中等 | 与 752 同题，是本题「字符串状态 BFS」模板的另一个落点 |