LeetCode 127. 单词接龙
题目描述
题意分析
每次恰好改变一个小写字母，变换后的单词必须在词表中，求从
beginWord到endWord的最短序列包含多少个单词。起点不必在词表中，终点必须在词表中；题目保证两端不同且所有单词等长。无法接龙时返回 0，答案包含起点和终点。
解法：双向 BFS
核心思路
[!blue]
把单词看作节点，恰好相差一个字母的两个单词之间连边。每次转换的代价都相同，因此最少转换次数就是无权图的最短距离。无需显式建图：枚举一个单词的每个位置，再尝试其他小写字母，即可找出所有可能的邻居。
从起点和终点同时进行 BFS。
front、back分别保存两侧尚未扩展的当前层，同一集合中的单词到对应起点的距离相同。每轮扩展节点较少的一侧，生成完整下一层；交换集合只改变扩展方向，不改变每侧按层推进的顺序。
dictionary只保存两侧都未访问过的单词。候选在另一侧当前层中，说明两条搜索路径可以通过这次转换接起来；否则，只有候选仍在词典中时才加入下一层，并立即从词典删除，防止多个节点重复加入它。相遇检查必须在词典检查之前，因为另一侧当前层的单词也已经从词典删除。双向 BFS 仍能保证第一次相遇最短：两侧更浅的层都已经扩展，若有更短路径，就应当在这些层之间更早相遇。只需检查另一侧当前层，因为更早的层已经检查过全部邻居；一条通往这些旧层的连接，不会等到以后才由未访问节点发现。扩展较小一侧只减少本轮工作量，不会跳过任一侧的层。
设当前两侧层到各自起点的边数为
a、b，代码维护steps = a + b + 1。两层之间再连一条边后，共有a + b + 1次转换，即steps + 1个单词。每完成一层扩展，一侧深度增加 1，所以steps++；即使交换两侧，深度之和也不变。每个字符位置尝试完后恢复原字符，保证下一位置仍然只改动一位。若任一侧前沿耗尽仍未相遇，该侧已经无法继续到达新单词，两端不连通，返回 0。
解题步骤
- 将词表放入哈希集合；若不含
endWord，直接返回 0。front从beginWord出发，back从endWord出发，并从待访问词典中删除两端。- 若
front比back大，就交换两侧集合，保证扩展较小的front。- 枚举
front中每个单词的一位替换：若候选在back中，返回steps + 1；若仍在词典中，删除并加入下一层。- 当前层扩展完后令
front = nextLevel、steps++；任一侧为空仍未相遇则返回 0。
代码实现
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)$，
n为词表大小，L为单词长度。每个单词至多被扩展一次，枚举 $26L$ 个候选，构造字符串及哈希查询需 $O(L)$。双向搜索主要减少实际访问节点数，不改变最坏上界。- 空间复杂度：$O(nL)$，用于词典和两侧搜索集合。
关键点总结
[!green]
- 这是隐式无权图最短路：动态生成邻居，不必显式建图。
- 每轮扩展完整一层，较小前沿决定扩展方向，
steps始终等于两侧深度之和加一。- 访问标记必须在加入下一层时完成，而不是出队时完成。
- 相遇时连接的是两侧当前层，返回转换次数加一，才是题目要求的单词数。
易错点总结
[!yellow]
- 未先确认
endWord在词表中，会接受题目规定之外的终点。steps从 0 开始会返回变换次数，而题目要的是单词个数。- 替换某一位后忘记恢复原字符，会污染下一位置的候选。
- 访问到候选却不立刻从词典删除，会让同一层重复加入该单词。
- 先检查另一前沿再查词典：前沿中的单词已经被删除，顺序反过来会漏掉相遇。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 433. 最小基因变化 | 中等 | 同样在单字符变化构成的状态图上求最少变化，原题基因串固定长度且候选较少。 |
| 126. 单词接龙 II | 困难 | 同样求最短单词变化，原题还需保留所有最短前驱以输出全部路径。 |
| 752. 打开转盘锁 | 中等 | 把合法状态及一次操作建成无权图进行 BFS；本题相差一个字符的单词之间连边，该题按转动一位数字扩展状态。 |
| 773. 滑动谜题 | 困难 | 把合法状态及一次操作建成无权图进行 BFS；本题相差一个字符的单词之间连边，该题按空位交换扩展棋盘状态。 |
| 1091. 二进制矩阵中的最短路径 | 中等 | 把合法状态及一次操作建成无权图进行 BFS；本题相差一个字符的单词之间连边，该题按可通行的相邻单元扩展路径。 |