LeetCode 126. 单词接龙 II
目录
题目描述
题意分析
从
beginWord出发，每次只能改动一个字母，且改动后的词必须在wordList里，要走到endWord。要求返回所有最短的转换序列，而不是最短长度，也不是任意一条。
「所有最短」这四个字决定了整道题的结构。它拆成两个子目标：先确定最短是多少，再枚举出所有达到这个长度的路径。这两件事必须分开做——只求一条最短路的算法拿不到全部方案，而直接枚举全部路径又会因为路径数爆炸而失控。
beginWord不要求在wordList中，但endWord必须在，否则无解。这一点决定了要先做一次存在性检查。
规模：
wordList最多 5000 个词，每个词长度不超过 10，只含小写字母。词长很短意味着「枚举每一位换成 26 个字母」这种生成邻居的方式是划算的——单个词的邻居生成代价是 $O(L \cdot 26)$，比两两比较所有词的 $O(N \cdot L)$ 要好。
一个容易被忽略的陷阱：最短路径可能有很多条，某个中间词可能同时被多个前驱到达，也可能被同一层的多个词到达。所以「访问过就跳过」这种单路最短路的剪枝会漏掉方案，必须改成「同层可以重复到达，跨层才禁止」。
边界：
endWord不在词表中、beginWord与endWord只差一个字母、存在多条等长路径共享中间节点、图不连通。
解法：BFS 分层 + 回溯输出
核心思路
把单词看成无权图的节点，相差一个字母的两个单词之间有边。题目要求的是全部最短路径：BFS 负责确定最短层次并建立最短路前驱图，随后 DFS 只在这张图上回溯答案。
定义
parents[next]为所有能在最短路上一步到达next的前驱。BFS 中的visited只包含更早层已经确认距离的单词；当前层新发现的单词暂存在nextLevel，整层结束后才并入visited。分层不变量：开始处理距离为
d的一层时，visited恰好包含距离小于等于d的节点；本层产生的每条前驱边都从距离d+1的节点指向距离d的节点。 同一个下一层单词可以记录多个本层前驱，但只在首次发现时入队一次。延迟更新访问集合是收集全部最短路径的关键。若
dog和log位于同一层且都能到达cog，立即标记cog会漏掉第二个前驱；层末统一标记则会保留二者。另一方面，更早层的节点已经在visited中，不会形成回边或更长路径。第一次发现
endWord时已经确定最短距离，但仍要处理完当前层，收齐终点的其他同层前驱；之后不再扩展更深层。前驱边的层号严格递减，因此反向 DFS 不会成环，且生成的每条路径长度都等于最短距离。正确性来自两点：BFS 只记录相邻层之间的边，所以回溯不会生成非最短路径；对下一层节点记录当前层的所有前驱，并在命中终点的整层结束后才停止，所以任何最短路径上的边都不会遗漏。
解题步骤
- 把词表放入哈希集合；若不含
endWord，直接返回空结果。- 将
beginWord入队并加入visited。- 逐层 BFS。对本层每个单词，枚举每个位置的 25 种有效替换。
- 候选词必须在词表中，且不能属于更早层；满足时把当前词加入
parents[candidate]。- 候选词在本层第一次出现时才加入
nextLevel和队列；整层结束后再将nextLevel合入visited。- 发现终点后完成当前层并停止 BFS；从
endWord沿前驱反向回溯到beginWord。样例
hit -> cog中，BFS 得到parents[cog] = [dog, log]，继续向前分别连接到dot和lot，最终输出：hit -> hot -> dot -> dog -> cog hit -> hot -> lot -> log -> cog若
endWord不在词表中则无解；若起点与终点只差一个字母，第一层会记录endWord <- beginWord，回溯直接得到长度为 2 的序列。
代码实现
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
class Solution {
public List<List<String>> findLadders(
String beginWord, String endWord, List<String> wordList) {
Set<String> dictionary = new HashSet<>(wordList);
List<List<String>> answer = new ArrayList<>();
if (!dictionary.contains(endWord)) {
return answer;
}
Map<String, List<String>> parents = new HashMap<>();
Queue<String> queue = new ArrayDeque<>();
Set<String> visited = new HashSet<>();
queue.offer(beginWord);
visited.add(beginWord);
boolean found = false;
while (!queue.isEmpty() && !found) {
int levelSize = queue.size();
Set<String> nextLevel = new HashSet<>();
for (int count = 0; count < levelSize; count++) {
String word = queue.poll();
char[] chars = word.toCharArray();
for (int i = 0; i < chars.length; i++) {
char original = chars[i];
for (char letter = 'a'; letter <= 'z'; letter++) {
if (letter == original) {
continue;
}
chars[i] = letter;
String next = new String(chars);
if (!dictionary.contains(next) || visited.contains(next)) {
continue;
}
parents.computeIfAbsent(next, key -> new ArrayList<>()).add(word);
if (nextLevel.add(next)) {
queue.offer(next);
}
if (next.equals(endWord)) {
found = true;
}
}
chars[i] = original;
}
}
visited.addAll(nextLevel);
}
if (!found) {
return answer;
}
Deque<String> path = new ArrayDeque<>();
path.addFirst(endWord);
buildPaths(endWord, beginWord, parents, path, answer);
return answer;
}
private void buildPaths(
String word,
String beginWord,
Map<String, List<String>> parents,
Deque<String> path,
List<List<String>> answer) {
if (word.equals(beginWord)) {
answer.add(new ArrayList<>(path));
return;
}
for (String parent : parents.getOrDefault(word, List.of())) {
path.addFirst(parent);
buildPaths(parent, beginWord, parents, path, answer);
path.removeFirst();
}
}
}
func findLadders(beginWord string, endWord string, wordList []string) [][]string {
dictionary := make(map[string]struct{}, len(wordList))
for _, word := range wordList {
dictionary[word] = struct{}{}
}
if _, exists := dictionary[endWord]; !exists {
return [][]string{}
}
parents := make(map[string][]string)
visited := map[string]struct{}{beginWord: {}}
queue := []string{beginWord}
found := false
for len(queue) > 0 && !found {
currentLevel := queue
queue = nil
nextLevel := make(map[string]struct{})
for _, word := range currentLevel {
chars := []byte(word)
for i := range chars {
original := chars[i]
for letter := byte('a'); letter <= byte('z'); letter++ {
if letter == original {
continue
}
chars[i] = letter
next := string(chars)
if _, exists := dictionary[next]; !exists {
continue
}
if _, exists := visited[next]; exists {
continue
}
parents[next] = append(parents[next], word)
if _, exists := nextLevel[next]; !exists {
nextLevel[next] = struct{}{}
queue = append(queue, next)
}
if next == endWord {
found = true
}
}
chars[i] = original
}
}
for word := range nextLevel {
visited[word] = struct{}{}
}
}
if !found {
return [][]string{}
}
answer := make([][]string, 0)
path := []string{endWord}
buildPaths126(endWord, beginWord, parents, path, &answer)
return answer
}
func buildPaths126(
word string,
beginWord string,
parents map[string][]string,
path []string,
answer *[][]string,
) {
if word == beginWord {
sequence := make([]string, len(path))
for i := range path {
sequence[len(path)-1-i] = path[i]
}
*answer = append(*answer, sequence)
return
}
for _, parent := range parents[word] {
path = append(path, parent)
buildPaths126(parent, beginWord, parents, path, answer)
path = path[:len(path)-1]
}
}
复杂度分析
设词表大小为
N，单词长度为L，最短路前驱边数为E，最终有P条路径，每条含至多D个单词。
- 时间复杂度： $O(NL^2 + PD)$。BFS 对每个单词枚举
25L个候选，构造并哈希长度为L的字符串；回溯复制每条输出路径。- 空间复杂度： 不含输出为 $O(NL + E + D)$，分别来自单词集合、前驱图和搜索路径；返回结果本身为 $O(PD)$。
关键点总结
- “所有最短路径”应拆成 BFS 建最短路图、DFS 枚举图中路径两个阶段。
visited只屏蔽更早层；当前层发现的节点延后到层末标记，才能保留多个最短前驱。- 前驱记录与入队必须分开：每个合法前驱都记录，同一个下一层节点只入队一次。
- 首次找到终点后要完成当前层，但不能继续更深层。
- 前驱图方向是“后继指向前驱”，回溯时层号严格递减，因此只生成最短路径且无需额外判环。
- 复杂度必须包含输出规模；最短路径条数可能很大，输出成本无法省略。
易错点总结
- 发现候选词后立即加入全局
visited： 会漏掉同一层的其他前驱；样例中可能只保留dog -> cog，丢失log -> cog。- 命中
endWord立刻退出： 当前层尚未处理的节点仍可能是终点的最短前驱。- 把前驱表建成
parent -> child却仍从终点回溯： 查不到前驱，结果为空；本实现固定使用child -> parents。- 当前层重复发现节点时再次入队： 不会漏答案，但会重复扩展同一个词，使搜索量急剧增加。
- 修改字符后不恢复原字符： 下一位置的替换会建立在错误单词上，合法邻居被漏掉。
- 只用 BFS 保存一个前驱： 可以还原一条最短路径，却不能输出所有最短路径。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 127. 单词接龙 | 困难 | 只要最短长度，可以一发现就标记访问，还能上双向 BFS |
| 433. 最小基因变化 | 中等 | 字符集只有 4 个、串长固定 8，是同一模型的最小化版本 |
| 301. 删除无效的括号 | 困难 | 同为「求所有最少操作方案」，用逐层 BFS 加结果集去重 |
| 752. 打开转盘锁 | 中等 | 邻居由数字轮盘生成，额外需要把死亡数字并入初始访问集合 |