Article / 文章
LeetCode 第127题：单词接龙
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk： - 每一对相邻的单词只差一个字母。 - 对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中
题目描述
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
- 每一对相邻的单词只差一个字母。
- 对于
1 <= i <= k时，每个si都在wordList中。注意，beginWord不需要在wordList中。 sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。
难度
中等
题目链接
示例
示例 1：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。示例 2：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。提示
1 <= beginWord.length <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthbeginWord、endWord和wordList[i]由小写英文字母组成beginWord != endWordwordList中的所有字符串 互不相同
解题思路
方法一：广度优先搜索（BFS）
这道题本质上是求解从beginWord到endWord的最短路径长度，非常适合使用BFS来解决。
关键点：
- 将单词看作图中的节点，如果两个单词只差一个字母，则它们之间有一条边
- 使用BFS从beginWord开始，逐层向外扩展，直到找到endWord或者搜索完所有可能的路径
- 记录搜索的层数，即为最短转换序列的长度
具体步骤：
- 将wordList转换为HashSet，便于快速查找
- 创建一个队列，将beginWord加入队列，并标记为已访问
- 初始化层数level为1（包含beginWord）
- 进行BFS：
- 获取当前队列中的单词数量size
- 遍历这些单词，对于每个单词，尝试修改其中的一个字符，看是否能得到wordList中的单词
- 如果找到了endWord，返回当前层数level+1
- 如果找到了wordList中的其他单词，将其加入队列，并从wordList中移除（标记为已访问）
- 处理完当前层的所有单词后，level加1
- 如果队列为空，说明无法找到从beginWord到endWord的路径，返回0
时间复杂度：O(N * C^2)，其中N是wordList的长度，C是单词的长度。对于每个单词，我们需要尝试C个位置，每个位置有26个字母，总共需要O(C * 26)的时间。 空间复杂度：O(N)，需要存储访问过的单词。
方法二：双向广度优先搜索
为了进一步优化BFS的效率，我们可以使用双向BFS，即从beginWord和endWord同时开始搜索，当两个搜索相遇时，就找到了最短路径。
关键点：
- 使用两个集合，分别表示从beginWord和endWord开始的搜索前沿
- 每次选择较小的集合进行扩展，以减少搜索空间
- 如果两个搜索相遇，则找到了最短路径
具体步骤：
- 将wordList转换为HashSet，便于快速查找
- 如果endWord不在wordList中，直接返回0
- 创建两个集合beginSet和endSet，分别包含beginWord和endWord
- 创建一个集合visited记录已访问的单词，初始为空
- 初始化层数level为1
- 进行双向BFS：
- 如果beginSet为空，说明无法找到路径，返回0
- 如果beginSet的大小大于endSet，交换beginSet和endSet（始终从较小的集合开始搜索）
- 创建一个新的集合nextBeginSet，用于存储下一层的单词
- 遍历beginSet中的每个单词，尝试修改其中的一个字符，看是否能得到wordList中的单词
- 如果找到的单词在endSet中，说明两个搜索相遇，返回level+1
- 如果找到的单词在wordList中且未被访问过，将其加入nextBeginSet和visited
- 处理完当前层的所有单词后，将nextBeginSet赋值给beginSet，level加1
- 如果搜索结束仍未找到路径，返回0
时间复杂度：O(N * C^2)，其中N是wordList的长度，C是单词的长度。虽然时间复杂度的上界与普通BFS相同，但在实际运行中，双向BFS通常能够显著减少搜索空间。 空间复杂度：O(N)，需要存储访问过的单词。
图解思路
BFS过程分析表
以示例1为例：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
| 层数 | 当前队列 | 已访问单词 | 下一层队列 | 说明 |
|---|---|---|---|---|
| 1 | [“hit”] | [“hit”] | [“hot”] | 从hit可以到达hot |
| 2 | [“hot”] | [“hit”, “hot”] | [“dot”, “lot”] | 从hot可以到达dot和lot |
| 3 | [“dot”, “lot”] | [“hit”, “hot”, “dot”, “lot”] | [“dog”, “log”] | 从dot可以到达dog，从lot可以到达log |
| 4 | [“dog”, “log”] | [“hit”, “hot”, “dot”, “lot”, “dog”, “log”] | [“cog”] | 从dog和log都可以到达cog |
| 5 | [“cog”] | [“hit”, “hot”, “dot”, “lot”, “dog”, “log”, “cog”] | [] | 找到endWord，返回层数5 |
双向BFS过程分析表
| 层数 | beginSet | endSet | visited | 下一层beginSet | 说明 |
|---|---|---|---|---|---|
| 1 | [“hit”] | [“cog”] | [“hit”, “cog”] | [“hot”] | 从hit可以到达hot |
| 2 | [“hot”] | [“cog”] | [“hit”, “cog”, “hot”] | [“dot”, “lot”] | 从hot可以到达dot和lot |
| 3 | [“dot”, “lot”] | [“cog”] | [“hit”, “cog”, “hot”, “dot”, “lot”] | [“dog”, “log”] | 从dot可以到达dog，从lot可以到达log |
| 4 | [“dog”, “log”] | [“cog”] | [“hit”, “cog”, “hot”, “dot”, “lot”, “dog”, “log”] | - | 从dog可以到达cog，两个搜索相遇，返回层数4+1=5 |
代码实现
C# 实现
public class Solution {
public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
// 将wordList转换为HashSet，便于快速查找
HashSet<string> wordSet = new HashSet<string>(wordList);
// 如果endWord不在wordList中，直接返回0
if (!wordSet.Contains(endWord)) {
return 0;
}
// 创建队列，用于BFS
Queue<string> queue = new Queue<string>();
queue.Enqueue(beginWord);
// 记录已访问的单词
HashSet<string> visited = new HashSet<string>();
visited.Add(beginWord);
// 初始化层数
int level = 1;
// BFS
while (queue.Count > 0) {
int size = queue.Count;
// 处理当前层的所有单词
for (int i = 0; i < size; i++) {
string currentWord = queue.Dequeue();
// 尝试修改当前单词的每一个字符
char[] chars = currentWord.ToCharArray();
for (int j = 0; j < chars.Length; j++) {
char originalChar = chars[j];
// 尝试替换为a-z的每个字符
for (char c = 'a'; c <= 'z'; c++) {
if (c == originalChar) continue;
chars[j] = c;
string newWord = new string(chars);
// 如果找到了endWord，返回当前层数+1
if (newWord == endWord) {
return level + 1;
}
// 如果新单词在wordSet中且未被访问过
if (wordSet.Contains(newWord) && !visited.Contains(newWord)) {
queue.Enqueue(newWord);
visited.Add(newWord);
}
}
// 恢复原字符
chars[j] = originalChar;
}
}
// 当前层处理完毕，层数加1
level++;
}
// 无法找到路径，返回0
return 0;
}
}Python 实现
from collections import deque
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
# 将wordList转换为集合，便于快速查找
word_set = set(wordList)
# 如果endWord不在wordList中，直接返回0
if endWord not in word_set:
return 0
# 创建队列，用于BFS
queue = deque([beginWord])
# 记录已访问的单词
visited = set([beginWord])
# 初始化层数
level = 1
# BFS
while queue:
size = len(queue)
# 处理当前层的所有单词
for _ in range(size):
current_word = queue.popleft()
# 尝试修改当前单词的每一个字符
for i in range(len(current_word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
if c == current_word[i]:
continue
new_word = current_word[:i] + c + current_word[i+1:]
# 如果找到了endWord，返回当前层数+1
if new_word == endWord:
return level + 1
# 如果新单词在word_set中且未被访问过
if new_word in word_set and new_word not in visited:
queue.append(new_word)
visited.add(new_word)
# 当前层处理完毕，层数加1
level += 1
# 无法找到路径，返回0
return 0C++ 实现
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
// 将wordList转换为unordered_set，便于快速查找
unordered_set<string> wordSet(wordList.begin(), wordList.end());
// 如果endWord不在wordList中，直接返回0
if (wordSet.find(endWord) == wordSet.end()) {
return 0;
}
// 创建队列，用于BFS
queue<string> q;
q.push(beginWord);
// 记录已访问的单词
unordered_set<string> visited;
visited.insert(beginWord);
// 初始化层数
int level = 1;
// BFS
while (!q.empty()) {
int size = q.size();
// 处理当前层的所有单词
for (int i = 0; i < size; i++) {
string currentWord = q.front();
q.pop();
// 尝试修改当前单词的每一个字符
for (int j = 0; j < currentWord.size(); j++) {
char originalChar = currentWord[j];
// 尝试替换为a-z的每个字符
for (char c = 'a'; c <= 'z'; c++) {
if (c == originalChar) continue;
currentWord[j] = c;
// 如果找到了endWord，返回当前层数+1
if (currentWord == endWord) {
return level + 1;
}
// 如果新单词在wordSet中且未被访问过
if (wordSet.find(currentWord) != wordSet.end() &&
visited.find(currentWord) == visited.end()) {
q.push(currentWord);
visited.insert(currentWord);
}
}
// 恢复原字符
currentWord[j] = originalChar;
}
}
// 当前层处理完毕，层数加1
level++;
}
// 无法找到路径，返回0
return 0;
}
};执行结果
C# 实现
- 执行用时：368 ms
- 内存消耗：41.2 MB
Python 实现
- 执行用时：128 ms
- 内存消耗：17.5 MB
C++ 实现
- 执行用时：36 ms
- 内存消耗：13.8 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 368 ms | 41.2 MB | 执行速度较慢，内存消耗较高 |
| Python | 128 ms | 17.5 MB | 执行速度适中，内存消耗适中 |
| C++ | 36 ms | 13.8 MB | 执行速度最快，内存消耗最低 |
代码亮点
- 🎯 使用BFS算法高效求解最短路径问题
- 💡 使用HashSet存储单词列表和已访问单词，提高查找效率
- 🔍 通过逐个替换字符的方式生成相邻单词，避免构建完整的图
- 🎨 代码结构清晰，逻辑简单易懂
常见错误分析
- 🚫 忘记检查endWord是否在wordList中，导致不必要的搜索
- 🚫 没有正确处理已访问单词，导致死循环或重复访问
- 🚫 BFS实现不当，没有按层遍历，导致无法正确计算层数
- 🚫 字符替换逻辑错误，导致无法找到所有可能的相邻单词
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| BFS | O(N * C^2) | O(N) | 实现简单，思路清晰 | 在单词数量大时效率较低 |
| 双向BFS | O(N * C^2) | O(N) | 搜索效率更高，尤其是在单词数量大时 | 实现稍复杂 |
| 预处理 + BFS | O(N * C^2) | O(N * C) | 可以避免重复生成相邻单词 | 预处理需要额外空间和时间 |
相关题目
- LeetCode 126. 单词接龙 II - 困难
- LeetCode 433. 最小基因变化 - 中等
- LeetCode 752. 打开转盘锁 - 中等
- LeetCode 1091. 二进制矩阵中的最短路径 - 中等
- LeetCode 279. 完全平方数 - 中等