LeetCode 面试题 17.22. 单词转换
题目描述
题意分析
从
beginWord变成等长的endWord，每次只替换一个字母，每次新得到的词都必须在字典中。返回包含起词和终词的一条完整序列，无法转换则返回空列表。题目只要求任意可行序列，现有 BFS 实现会找到其中一条最短序列。
解法：BFS 最短路径
核心思路
[!blue]
把每个单词看作图中的节点，只相差一个字母的两个词之间连边。每次转换就是走一条边，所有边代价都是一次操作，因此从起词做广度优先搜索，可以按转换次数从少到多访问可达单词。
不必提前比较所有词来建图。取出一个词后，依次固定一个位置，把该位置尝试替换成
a到z中的其他字母，再用哈希集合检查候选词是否在字典中。每个位置尝试完后恢复原字符，保证下一位置仍从原单词出发，只改变一处。一个候选词第一次被发现时，立即标记已访问、记录
parent[next] = cur，然后入队。BFS 先扩展距离较小的节点，所以首次发现已经给出到这个词的最短路线；后续不必重复入队或覆盖前驱。题目只要一条路径，每个词保存一个前驱就足够。队列逐层处理，发现终词就能结束。由终词反复沿
parent向前，得到终点到起点的逆序路径，再整体反转。每个前驱都来自更早一层，因此链不会形成环；起词没有前驱，回溯到它之后停止，并且它本身也包含在结果中。起词作为搜索起点入队，不要求先由字典中的词转换得到。起终词相同则直接返回起词；否则终词不在字典中一定无解。如果终词在字典中但与起词不连通，队列最终会耗尽，同样返回空列表。
解题步骤
- 处理起终词相同的情况，建立字典集合；若终词不在集合中，返回空列表。
- 将起词入队并标记访问，初始化前驱映射。
- 逐层取词，按位置生成只改一个字母的候选；只接收在字典中且尚未访问的词。
- 首次发现时固定前驱并入队，发现终词后停止搜索。
- 从终词沿前驱回到起词，再反转顺序；如果未找到终词则返回空列表。
代码实现
// 广度优先搜索 从 beginWord 出发，首次到达 endWord 即为最短路径。
class Solution {
public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
if (beginWord.equals(endWord)) {
return List.of(beginWord);
}
Set<String> dict = new HashSet<>(wordList);
if (!dict.contains(endWord)) {
return new ArrayList<>();
}
Queue<String> queue = new ArrayDeque<>();
Map<String, String> parent = new HashMap<>();
Set<String> visited = new HashSet<>();
queue.offer(beginWord);
visited.add(beginWord);
boolean found = false;
while (!queue.isEmpty() && !found) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String cur = queue.poll();
char[] arr = cur.toCharArray();
for (int p = 0; p < arr.length; p++) {
char old = arr[p];
for (char c = 'a'; c <= 'z'; c++) {
if (c == old) {
continue;
}
arr[p] = c;
String next = new String(arr);
if (!dict.contains(next) || visited.contains(next)) {
continue;
}
visited.add(next);
// 首次发现时固定前驱，回溯得到一条合法最短路径。
parent.put(next, cur);
queue.offer(next);
if (next.equals(endWord)) {
found = true;
break;
}
}
// 恢复当前位置，下一位仍从原单词尝试替换。
arr[p] = old;
if (found) {
break;
}
}
if (found) {
break;
}
}
}
if (!found) {
return new ArrayList<>();
}
List<String> path = new ArrayList<>();
String cur = endWord;
while (cur != null) {
path.add(cur);
cur = parent.get(cur);
}
// 前驱回溯得到终点到起点，反转成题目要求的顺序。
Collections.reverse(path);
return path;
}
}
// 广度优先搜索 从 beginWord 出发，首次到达 endWord 即为最短路径。
func findLadders(beginWord string, endWord string, wordList []string) []string {
if beginWord == endWord {
return []string{
beginWord,
}
}
dict := map[string]bool{}
for _, w := range wordList {
dict[w] = true
}
if !dict[endWord] {
return []string{}
}
queue := []string{
beginWord,
}
visited := map[string]bool{beginWord: true}
parent := map[string]string{}
found := false
for head := 0; head < len(queue) && !found; {
size := len(queue) - head
for i := 0; i < size; i++ {
cur := queue[head]
head++
arr := []byte(cur)
for p := 0; p < len(arr); p++ {
old := arr[p]
for c := byte('a'); c <= byte('z'); c++ {
if c == old {
continue
}
arr[p] = c
next := string(arr)
if !dict[next] || visited[next] {
continue
}
visited[next] = true
// 首次发现时固定前驱，回溯得到一条合法最短路径。
parent[next] = cur
queue = append(queue, next)
if next == endWord {
found = true
break
}
}
// 恢复当前位置，下一位仍从原单词尝试替换。
arr[p] = old
if found {
break
}
}
if found {
break
}
}
}
if !found {
return []string{}
}
path := make([]string, 0)
cur := endWord
for cur != "" {
path = append(path, cur)
cur = parent[cur]
}
for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
// 前驱回溯得到终点到起点，反转成题目要求的顺序。
path[i], path[j] = path[j], path[i]
}
return path
}
复杂度分析
- 时间复杂度：期望 $O((W+1)L^2)$，其中
W为字典大小，L为输入单词的最大长度。最多展开W+1个词，每词尝试常数倍的L个候选，构造候选字符串及计算哈希各需 $O(L)$。- 空间复杂度：$O((W+1)L)$，用于字典、已访问词、队列、前驱与恢复的路径。
关键点总结
[!green]
- 单字母替换构成等权图，BFS 首次发现即可确定最短距离。
- 入队时标记并固定前驱，既去重又留下路径恢复信息。
- 逐位置生成邻居后必须复原，回溯路径后必须反转。
易错点总结
[!yellow]
- 不恢复刚修改的位置，会生成同时改变多个字母的假邻居。
- 出队时才标记，会让同一个词在此前被多次入队；覆盖前驱还可能破坏已经确定的路径。
- 只返回经过的中间词，会漏掉题目所需的起词或终词。
- 直接返回前驱回溯结果，顺序会从终词指向起词。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 127. 单词接龙 | 困难 | 可复用BFS并记录前驱恢复完整序列，原题只返回最短变换长度。 |
| 126. 单词接龙 II | 困难 | 原题输出全部最短路径，本题只需一条可行完整序列，单个前驱即可用于恢复。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！