LeetCode 127. 单词接龙
目录
题目描述
题意分析
给定起点单词
beginWord、终点单词endWord和一份词表，每次只能改变单词中的一个字符，且变换后的每一个中间单词都必须出现在词表里，问从起点变到终点最少需要经过多少个单词。注意返回的是序列里单词的个数，不是变换次数，起点和终点都算在内，所以答案总比变换次数多 1。这里有一条必须先点明的规则：
endWord本身也是「变换后的单词」，因此它必须在词表中，否则无论怎么变都到不了，直接返回 0。反过来beginWord不要求在词表里，它是免检的起点。这一条不看清楚会写出永远跑不完或者答案偏差的代码。约束里的信号：所有单词等长且只含小写字母，长度很短（10 量级），词表规模在数千。等长意味着「相差一个字符」这个关系判定简单；只含小写字母意味着一个位置最多 26 种取值；词表不大意味着可以整体放进哈希集合做 $O(1)$ 判存。另外题目保证
beginWord != endWord，且词表内单词互不相同。边界包括：
endWord不在词表中（返回 0）；起点与终点只差一个字符且终点在词表里（答案为 2）；词表里存在与起点重名的单词（要防止绕回起点）；以及词表虽大但与起点完全不连通（BFS 自然耗尽队列返回 0）。
解法：双向 BFS
核心思路
把单词视为图节点，只差一个字符的两个单词之间有一条无权边，问题就是最短路。无需两两比较建图：枚举每个位置的 26 种替换，再用哈希集合判断候选是否存在即可。
普通 BFS 已能保证最短，但分支很多时会搜索约 $b^d$ 个状态。双向 BFS 同时从起点和终点按层搜索，每轮扩展节点较少的一侧，通常把规模降到约 $2b^{d/2}$。
循环不变量是：
front、back分别保存两端当前层的节点，steps等于两侧当前深度之和再加 1（已计入起点）；词典只保留两边都未访问的单词。每扩展任意一侧的一层，steps都加 1，所以交换前沿后也无需交换距离变量。生成的邻居若在另一侧当前层中，两棵 BFS 树第一次相交，因两边都逐层扩展，得到的路径必为最短。邻居一旦进入下一层就从词典删除，避免重复访问。
解题步骤
- 将词表放入哈希集合；若不含
endWord，直接返回 0。front从beginWord出发，back从endWord出发，并从待访问词典中删除两端。- 每轮交换两侧集合，保证只扩展较小的
front。- 枚举
front中每个单词的一位替换：若候选在back中，返回steps + 1；若仍在词典中，删除并加入下一层。- 当前层扩展完后令
front = next、steps++；任一侧为空仍未相遇则返回 0。例：
hit → hot → dot → dog → cog包含 5 个单词，因此返回 5，而不是 4 次变换。修改完一个位置后必须恢复原字符，再枚举下一位置。
代码实现
import java.util.HashSet;
import java.util.List;
import java.util.Set;
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> dictionary = new HashSet<>(wordList);
if (!dictionary.contains(endWord)) {
return 0;
}
Set<String> front = new HashSet<>();
Set<String> back = new HashSet<>();
front.add(beginWord);
back.add(endWord);
dictionary.remove(beginWord);
dictionary.remove(endWord);
int steps = 1;
while (!front.isEmpty() && !back.isEmpty()) {
if (front.size() > back.size()) {
Set<String> temp = front;
front = back;
back = temp;
}
Set<String> nextLevel = new HashSet<>();
for (String word : front) {
char[] chars = word.toCharArray();
for (int idx = 0; idx < chars.length; idx++) {
char original = chars[idx];
for (char ch = 'a'; ch <= 'z'; ch++) {
if (ch == original) continue;
chars[idx] = ch;
String next = new String(chars);
if (back.contains(next)) return steps + 1;
if (dictionary.remove(next)) nextLevel.add(next);
}
chars[idx] = original;
}
}
front = nextLevel;
steps++;
}
return 0;
}
}
func ladderLength(beginWord string, endWord string, wordList []string) int {
dictionary := make(map[string]bool, len(wordList))
for _, word := range wordList {
dictionary[word] = true
}
if !dictionary[endWord] {
return 0
}
front := map[string]bool{beginWord: true}
back := map[string]bool{endWord: true}
delete(dictionary, beginWord)
delete(dictionary, endWord)
steps := 1
for len(front) > 0 && len(back) > 0 {
if len(front) > len(back) {
front, back = back, front
}
nextLevel := make(map[string]bool)
for word := range front {
chars := []byte(word)
for idx := 0; idx < len(chars); idx++ {
original := chars[idx]
for ch := byte('a'); ch <= byte('z'); ch++ {
if ch == original { continue }
chars[idx] = ch
next := string(chars)
if back[next] { return steps + 1 }
if !dictionary[next] { continue }
delete(dictionary, next)
nextLevel[next] = true
}
chars[idx] = original
}
}
front = nextLevel
steps++
}
return 0
}
复杂度分析
- 时间复杂度：最坏为 $O(n \cdot 26 \cdot L^2)$。每个单词至多被扩展一次，枚举 $26L$ 个候选，构造字符串需 $O(L)$。双向搜索主要优化实际搜索宽度，不改变最坏上界。
- 空间复杂度：$O(nL)$，用于词典和两侧搜索集合。
关键点总结
- 这是隐式无权图最短路：动态生成邻居，不必显式建图。
- 双向 BFS 每轮扩展较小前沿，减少分支爆炸；交换集合不改变两侧已走的总层数。
- 访问标记必须在加入下一层时完成，而不是出队时完成。
- 返回的是序列中的单词数，所以起点层为 1；若需输出所有最短路径，还要记录前驱关系。
易错点总结
- 未先确认
endWord在词表中，会接受题目规定之外的终点。steps从 0 开始会返回变换次数，而题目要的是单词个数。- 替换某一位后忘记恢复原字符，会污染下一位置的候选。
- 访问到候选却不立刻从词典删除，会让同一层重复加入该单词。
- 双向搜索只应交换两侧前沿集合，不能把两侧访问状态混回待访问词典。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| LCR 108. 单词接龙 | 困难 | 本题的同题异号版本 |
| 126. 单词接龙 II | 困难 | 记录前驱回溯所有最短路径 |
| 433. 最小基因变化 | 中等 | 字符集缩小为 4 的同型题 |
| 752. 打开转盘锁 | 中等 | 状态转移带死亡节点约束 |
| LCR 109. 打开转盘锁 | 中等 | 双向 BFS 的练手题 |
| 854. 相似度为 K 的字符串 | 困难 | 邻居生成靠交换而非替换 |
| 773. 滑动谜题 | 困难 | 棋盘状态编码成字符串 |
| 815. 公交路线 | 困难 | 以路线而非站点建图 |
| 909. 蛇梯棋 | 中等 | 二维棋盘展平成一维编号 |
| 1345. 跳跃游戏 IV | 困难 | 等值下标建边并及时清空 |
| 1654. 到家的最少跳跃次数 | 中等 | 带方向限制的状态扩展 |
| LCP 09. 最小跳跃次数 | 困难 | 单调边界配合 BFS 剪枝 |
| 542. 01 矩阵 | 中等 | 多源 BFS |
| LCR 107. 01 矩阵 | 中等 | 多源 BFS 的同题异号版本 |
| 994. 腐烂的橘子 | 中等 | 层数即时间步 |
| 1162. 地图分析 | 中等 | 求最短距离的最大值 |
| 1091. 二进制矩阵中的最短路径 | 中等 | 八连通网格最短路 |
| 1129. 颜色交替的最短路径 | 中等 | 状态里附带边的颜色 |
| 1293. 网格中的最短路径 | 困难 | 状态里附带剩余消除次数 |
| 1298. 你能从盒子里获得的最大糖果数 | 困难 | 依赖解锁的可达性搜索 |