LeetCode 面试题 17.22. 单词转换
目录
题目描述
题意分析
给定起始单词、目标单词和一本字典，每次只能改动一个字母，且改完之后得到的单词必须在字典里，要求返回一条完整的变换序列（含首尾），无解则返回空列表。注意题目要的是路径本身而不是路径长度，这一点直接决定了必须额外记录「每个单词是从谁变过来的」。
题面还有两个容易忽略的细节：所有单词长度相同，且都由小写字母组成。长度相同意味着变换只有「替换某一位」这一种形式，不存在插入或删除；只含小写字母意味着每一位的候选替换值最多 25 个（排除原字符），这是一个非常小的常数。
字典规模在几千到上万量级，单词长度不超过十几。这两个数字放在一起给出了强烈的信号：枚举「所有可能的邻居字符串」再查字典，比两两比较字典中的单词更划算。前者对每个单词是 $L \times 25$ 次查表，后者是 $O(n L)$ 次逐字符比对，当 n 远大于 $25L$ 时前者胜出。
边界上要考虑：起始词和目标词可能相同，此时答案就是只含一个词的序列；目标词可能根本不在字典里，直接无解；起始词自身不一定在字典里，不能想当然地把它当成字典元素处理；字典里也可能存在孤立的单词群，导致从起点根本走不到终点。
解法：BFS 最短路径
核心思路
最朴素的做法是从起始词开始做深度优先枚举：每一步尝试所有可达的字典单词，一路递归到目标词为止。这在稠密的字典上会退化成指数级的路径枚举——同一个中间单词可能被无数条前缀不同的路径重复访问，而它们后续的探索完全一样，做的是大量重复劳动。
瓶颈的本质是没有把「单词」当成状态去做去重。事实上，一旦确定当前手里是哪个单词，接下来能走到哪些地方就完全确定了，与「我是怎么走到这里的」无关。这正是图论模型成立的条件。
于是把每个单词看成图上的一个点，两个单词若只差一个字母就在它们之间连一条无权边。问题立刻变成「在这张图上求从起点到终点的一条路径」。由于边权全为 1，逐层向外扩展的搜索顺序天然保证：任何单词第一次被访问到时，走过的步数就是从起点到它的最短距离，这就是可以对每个单词只访问一次、直接打上已访问标记的理论依据。
算法维持的不变量有两条。其一，队列中的元素按到起点的距离非递减排列，同一轮循环处理的是同一层；其二，
parent[w]一旦被写入就不再修改，它记录的是首次到达 w 时的前驱，因而沿 parent 从终点一路回溯，得到的必然是一条合法且最短的路径。邻居的产生方式选择「构造而非比较」：把当前单词拆成字符数组，对每一位依次替换成其余 25 个字母，拼出新串后到字典哈希集合里查一次。这样每个单词的扩展代价是 $O(L \times 26)$ 次哈希查询，与字典总规模无关，比遍历整本字典逐个比较要稳得多。
最后，因为题目只要求返回任意一条合法序列而非全部序列，一旦目标词入队就可以立刻停止扩展——继续搜下去也只会找到不更短的路径。
解题步骤
- 先处理起点等于终点的退化情况，直接返回只含它自己的列表。这是因为后续的搜索逻辑建立在「至少变换一次」之上，起点从不进入邻居枚举的判定，不特判会走到「未找到」分支返回空列表。
- 把字典装进哈希集合，并检查目标词是否在其中，不在则立刻返回空。装集合是为了把「某个拼出来的串是否合法」降到常数判定；提前检查目标词则能在无解时省掉整轮搜索，也避免了搜索成功却无法回溯的矛盾状态。
- 初始化队列放入起点，同时把起点加入已访问集合。访问标记必须在入队时打，而不是出队时打，否则同一层里两个不同单词可能各自把同一个邻居塞进队列，造成重复扩展和 parent 被覆盖。
- 按层循环：先记下当前队列长度 size，再恰好弹出 size 个元素。这样每一轮内部处理的都是距离相同的一批单词，层与层之间界限清晰；虽然本题只要一条路径、不严格依赖分层，但这个写法能让「首次到达即最短」的性质一目了然，也便于扩展成需要层数的变体。
- 对每个出队单词，逐位尝试替换成 'a' 到 'z'，跳过与原字符相同的情形。跳过是因为替换成自己等于没变，会生成当前单词本身，白白多一次查表。替换后拼出新串，若不在字典中或已访问过则跳过；否则打标记、写 parent、入队。
- 每处理完一位后必须把该位复原。字符数组是复用的，不还原会导致后续位的枚举建立在已被污染的串上，生成大量本不存在的邻居。
- 一旦生成的邻居就是目标词，置标志位并层层跳出所有循环。三层循环各有一次 break 判断，是为了在不使用异常或标签跳转的前提下尽快退出。
- 从目标词沿 parent 反向回溯到起点，再整体反转。反转是必要的，因为回溯天然给出的是从终点到起点的逆序；起点的 parent 不存在（Java 中为 null、Go 中为空串），正好作为循环终止条件。
以
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]走一遍。起点终点不同，字典集合建好，cog在其中，继续。队列初始为["hit"]，visited = {hit}。第一层：弹出
hit。改第 0 位得到 ait…zit，其中只有…都不在字典；改第 1 位得到 hat、hbt…，其中hot在字典且未访问，于是 visited 加入 hot、parent["hot"] = "hit"、入队；改第 2 位得到 hia、hib… 均不在字典。本层结束，队列为["hot"]。第二层：弹出
hot。改第 0 位时试到dot（在字典、未访问），记parent["dot"] = "hot"入队；继续试到lot，记parent["lot"] = "hot"入队。改第 1 位得到 hat、hbt… 均不在字典（hit虽在起点但不在字典里，即使拼出来也会被字典判定挡掉）。改第 2 位得到 hoa、hob… 也都不在字典。本层结束，队列为["dot", "lot"]。第三层：弹出
dot，改第 2 位试到dog（在字典、未访问），记parent["dog"] = "dot"入队；dog不等于cog，继续。再弹出lot，改第 2 位试到log，记parent["log"] = "lot"入队。本层结束，队列为["dog", "log"]。第四层：弹出
dog，改第 0 位试到cog，它在字典且未访问，记parent["cog"] = "dog"入队，同时发现它等于终点，found 置真，逐层 break 退出。回溯阶段：从
cog出发，path = [cog]；parent["cog"] = "dog"，path = [cog, dog]；parent["dog"] = "dot"，path = [cog, dog, dot]；parent["dot"] = "hot"，path = [cog, dog, dot, hot]；parent["hot"] = "hit"，path = [cog, dog, dot, hot, hit]；hit没有 parent，循环结束。反转得到["hit", "hot", "dot", "dog", "cog"]，每相邻两词恰好差一个字母，且除首词外全部来自字典，答案合法。
代码实现
// 广度优先搜索 从 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(n \times L^2)$，其中 n 为字典单词数、L 为单词长度。凭什么？每个单词最多出队一次（已访问集合保证），出队后要枚举 L 个位置各 25 个替换字符，共约 $26L$ 次尝试；每次尝试都要用
new String(arr)构造一个长度为 L 的新串并做哈希，构造与哈希各是 $O(L)$，于是单个单词的扩展代价是 $O(26 L^2)$，乘以 n 个单词、去掉常数即得。回溯路径最多经过 n 个单词，量级更低不影响总和。- 空间复杂度：$O(n \times L)$。凭什么？字典集合、已访问集合、parent 映射和队列各自最多保存 n 个单词，每个单词占 L 个字符；这四个结构都是线性于字典规模的，没有二维邻接表这类平方级开销。
关键点总结
- 状态无后效性是图建模的前提：能否把问题抽象成图，判据是「当前状态是否唯一决定了后续所有可能」。本题中「手里是哪个单词」就是完整状态，历史路径不影响未来，因此可以对状态去重，把指数级枚举压成线性遍历。遇到「每步做一个小改动、问能否到达/最少几步」的题，先问自己这个问题。
- 边权全为 1 时逐层扩展即最短路：这是不需要优先队列、不需要松弛操作的关键理由。一旦题目给某些变换加上不同代价，这个性质立刻失效，必须换成带优先队列的最短路算法——面试中被追问「如果每种字母替换代价不同呢」，标准答案就是这个。
- 邻居的产生方式要按规模选择：「构造候选串再查字典」的代价是 $O(26L^2)$ 且与字典大小无关，「遍历字典逐个比较」的代价是 $O(nL)$。字典大而单词短时选前者，字典小而单词极长时选后者。能说清这个取舍，比背下模板更能体现工程判断。
- 要路径就得记前驱，且前驱只写一次：距离和路径是两种不同的输出需求。只要答案是路径，就必须维护 parent 映射，并且严格保证「首次到达时写入、之后永不覆盖」——这条不变量正是回溯结果最短且无环的保证。
- 访问标记的时机决定正确性与效率：入队即标记，可以避免同一层内多个单词把同一邻居重复入队；若改成出队才标记，队列规模会成倍膨胀，且 parent 可能被后写的路径覆盖。
- 面试视角：这题是「单词接龙」的简化版，考察点集中在建模而非算法本身。答题时先明确说出「把单词当节点、差一个字母连边、边权为 1」，再讲搜索顺序和 parent 回溯，最后主动提一句「如果要返回所有最短路径，就要把 parent 换成前驱列表并在同层允许多次记录」，能显著拉开与只会套模板的候选人的差距。
易错点总结
- 错误写法：忘记特判起点等于终点。用例
beginWord = "a", endWord = "a", wordList = ["a","b"]→ 搜索时枚举邻居会跳过与原字符相同的替换，永远生成不出a自己，found 保持假，返回空列表；正确答案是["a"]。- 错误写法：不检查终点是否在字典中。用例
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog"]→ 搜索会把整个连通块跑完才发现无解，虽然结果仍是空列表，但在字典达到万级时白白多跑一整轮；更糟的是若把「拼出的串等于终点」作为命中条件而绕过字典判定，会返回一条包含非法单词的路径。- 错误写法：出队时才把单词加入已访问集合。用例
beginWord = "hit", endWord = "cog", wordList = ["hot","hog","cog","dot","dog"]→ 同一层的dot和hot都能生成dog，两次都入队；第二次入队时parent["dog"]被覆盖成后来者，回溯出的前驱与实际最短路不符，且队列中出现重复元素导致后续层被重复扩展。- 错误写法：替换字符后忘记把该位复原。用例
beginWord = "hit", wordList = ["hot","hop"]→ 处理完第 1 位得到hot后，若不把 arr[1] 还原成i，枚举第 2 位时基串已变成ho?，会拼出hoa…hoz这批本不应从hit一步到达的串，一旦其中有字典单词（如hop）就会连出一条实际需要两步的假边，返回的序列相邻两词差了两个字母。- 错误写法：枚举替换字符时不跳过原字符。用例
beginWord = "hot", wordList = ["hot","dot"]→ 会生成hot自己，若它恰好在字典中且未被标记（例如起点未加入 visited），就会自己指向自己入队，parent 形成自环，回溯阶段陷入死循环直到栈溢出或超时。- 错误写法：回溯路径后忘记反转。用例
beginWord = "hit", endWord = "cog"→ 返回["cog","dog","dot","hot","hit"]，方向完全相反，判题按序列首元素必须等于 beginWord 校验，直接判错。- 错误写法：找到终点后不跳出，继续把整层扩展完。用例字典规模上万且终点在第一层就被找到 → 仍要枚举完当前层所有单词的全部邻居，多做数万次哈希查询；虽然结果正确，但在卡常数的数据下会超时。三层循环都要有跳出判断。
- 错误写法：Go 里用
for cur != ""回溯却让某个单词本身是空串。用例wordList含空字符串（越界数据）→ 循环提前终止，路径被截断；更常见的是把parent声明为map[string]string后误以为访问缺失键会 panic 而加了ok判断却写反条件，导致起点被漏进路径。稳妥做法是显式判断cur == beginWord后再终止。- 错误写法：Java 里用
String拼接生成邻居，例如cur.substring(0,p) + c + cur.substring(p+1)。用例字典一万词、单词长度 10 → 每次拼接产生三个临时对象，总共数百万次对象分配，虽然复杂度同阶但常数极大，在时限紧的判题环境下容易 TLE；复用char[]数组是标准做法。- 错误写法：把 beginWord 也当作字典成员加入 visited 之外的结构，或反过来假设它一定在字典里。用例
beginWord = "hit"而wordList不含hit→ 若代码在初始化时执行dict.remove(beginWord)之类的操作没问题，但若在扩展时要求「当前单词必须在字典中」才继续，起点会被直接排除，第一层就无法扩展，返回空列表。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 127. 单词接龙 | 困难 | 只要最短长度不要路径，可省去 parent 映射并用双向扩展把搜索规模开方 |
| 126. 单词接龙 II | 困难 | 要求列出全部最短路径，前驱必须存成列表且同层允许重复记录，去重时机完全不同 |
| 433. 最小基因变化 | 中等 | 字符集只有 ACGT 四种、串长固定为 8，可以用位压缩把状态编码成整数 |
| 752. 打开转盘锁 | 中等 | 邻居由数字环上下拨动生成而非查字典，还多了一组必须绕开的死亡状态 |
| 815. 公交路线 | 困难 | 节点应建在路线而非站点上，考察如何选择合适的状态定义来压缩边数 |
| 1091. 二进制矩阵中的最短路径 | 中等 | 图结构由网格八连通直接给出，无需构造邻居，重点在越界与障碍判定 |