LeetCode 第126题：单词接龙 II

题目描述

按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：

• 每对相邻的单词之间仅有单个字母不同。
• 转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
• sk == endWord

给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回。

难度

困难

题目链接

点击在LeetCode中查看题目

示例

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
解释：存在 2 种最短的转换序列：
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：[]
解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。

提示

• 1 <= beginWord.length <= 5
• endWord.length == beginWord.length
• 1 <= wordList.length <= 500
• wordList[i].length == beginWord.length
• beginWord、endWord 和 wordList[i] 由小写英文字母组成
• beginWord != endWord
• wordList 中的所有单词 互不相同

解题思路

方法一：BFS + DFS

这道题是“单词接龙”的扩展，不仅要找到最短路径的长度，还要找出所有的最短路径。我们可以使用BFS找到最短路径的长度，然后使用DFS找出所有的最短路径。

关键点：

• 使用BFS找到从beginWord到endWord的最短路径长度
• 在BFS过程中记录每个单词的前驱单词
• 使用DFS从endWord回溯到beginWord，找出所有的最短路径

具体步骤：

1. 使用BFS找到从beginWord到endWord的最短路径长度：
   • 将beginWord加入队列，并标记为已访问
   • 逐层遍历队列中的单词，对于每个单词，尝试修改其中的一个字符，看是否能得到wordList中的单词
   • 如果找到了endWord，记录当前的层数，即为最短路径长度
2. 在BFS过程中，记录每个单词的所有可能的前驱单词
3. 使用DFS从endWord回溯到beginWord，找出所有的最短路径：
   • 从endWord开始，根据前驱单词信息，回溯到beginWord
   • 记录所有长度等于最短路径长度的路径

时间复杂度：O(N * C^2 + a)，其中N是wordList的长度，C是单词的长度，a是所有可能的路径数量 空间复杂度：O(N * C + a)，其中N是wordList的长度，C是单词的长度，a是所有可能的路径数量

方法二：双向BFS + DFS

为了优化BFS的效率，我们可以使用双向BFS，即从beginWord和endWord同时开始搜索，当两个搜索相遇时，就找到了最短路径。

关键点：

• 使用两个队列，分别从beginWord和endWord开始搜索
• 每次选择较小的队列进行扩展，以减少搜索空间
• 记录每个单词的前驱和后继单词
• 使用DFS找出所有的最短路径

具体步骤：

1. 使用双向BFS找到从beginWord到endWord的最短路径长度：
   • 初始化两个队列，分别包含beginWord和endWord
   • 每次选择较小的队列进行扩展
   • 如果两个搜索相遇，记录当前的层数之和，即为最短路径长度
2. 在BFS过程中，记录每个单词的前驱和后继单词
3. 使用DFS从endWord回溯到beginWord，找出所有的最短路径

时间复杂度：O(N * C^2 + a)，其中N是wordList的长度，C是单词的长度，a是所有可能的路径数量 空间复杂度：O(N * C + a)，其中N是wordList的长度，C是单词的长度，a是所有可能的路径数量

图解思路

BFS过程分析表

以示例1为例：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]

层数	当前队列	下一层队列	前驱单词记录	说明
0	[“hit”]	[“hot”]	hot: [hit]	从hit可以到达hot
1	[“hot”]	[“dot”, “lot”]	dot: [hot], lot: [hot]	从hot可以到达dot和lot
2	[“dot”, “lot”]	[“dog”, “log”]	dog: [dot], log: [lot]	从dot可以到达dog，从lot可以到达log
3	[“dog”, “log”]	[“cog”]	cog: [dog, log]	从dog和log都可以到达cog
4	[“cog”]	[]	-	找到endWord，BFS结束

DFS回溯过程分析表

当前单词	前驱单词	当前路径	回溯结果
“cog”	[“dog”, “log”]	[“cog”]	分别从“dog”和“log”继续回溯
“dog”	[“dot”]	[“cog”, “dog”]	从“dot”继续回溯
“dot”	[“hot”]	[“cog”, “dog”, “dot”]	从“hot”继续回溯
“hot”	[“hit”]	[“cog”, “dog”, “dot”, “hot”]	从“hit”继续回溯
“hit”	[]	[“cog”, “dog”, “dot”, “hot”, “hit”]	回溯结束，得到一条路径
“log”	[“lot”]	[“cog”, “log”]	从“lot”继续回溯
“lot”	[“hot”]	[“cog”, “log”, “lot”]	从“hot”继续回溯
“hot”	[“hit”]	[“cog”, “log”, “lot”, “hot”]	从“hit”继续回溯
“hit”	[]	[“cog”, “log”, “lot”, “hot”, “hit”]	回溯结束，得到另一条路径

代码实现

C# 实现

public class Solution {
    public IList<IList<string>> FindLadders(string beginWord, string endWord, IList<string> wordList) {
        // 结果列表
        IList<IList<string>> res = new List<IList<string>>();
        
        // 将wordList转换为HashSet，便于快速查找
        HashSet<string> wordSet = new HashSet<string>(wordList);
        
        // 如果endWord不在wordList中，直接返回空列表
        if (!wordSet.Contains(endWord)) {
            return res;
        }
        
        // 记录每个单词的前驱单词
        Dictionary<string, List<string>> predecessors = new Dictionary<string, List<string>>();
        
        // BFS找到最短路径
        if (!BFS(beginWord, endWord, wordSet, predecessors)) {
            return res;
        }
        
        // DFS回溯找到所有最短路径
        List<string> path = new List<string> { endWord };
        DFS(endWord, beginWord, predecessors, path, res);
        
        return res;
    }
    
    private bool BFS(string beginWord, string endWord, HashSet<string> wordSet, Dictionary<string, List<string>> predecessors) {
        Queue<string> queue = new Queue<string>();
        HashSet<string> visited = new HashSet<string>();
        HashSet<string> toVisit = new HashSet<string>();
        
        queue.Enqueue(beginWord);
        toVisit.Add(beginWord);
        
        bool found = false;
        
        // 初始化每个单词的前驱列表
        foreach (string word in wordSet) {
            predecessors[word] = new List<string>();
        }
        predecessors[beginWord] = new List<string>();
        
        while (queue.Count > 0 && !found) {
            visited.UnionWith(toVisit);
            toVisit.Clear();
            
            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);
                        
                        // 如果新单词在wordSet中
                        if (wordSet.Contains(newWord)) {
                            // 如果找到了endWord
                            if (newWord == endWord) {
                                found = true;
                                predecessors[newWord].Add(currentWord);
                            }
                            // 如果新单词还没有被访问过
                            else if (!visited.Contains(newWord)) {
                                // 如果新单词还没有在当前层被访问过
                                if (!toVisit.Contains(newWord)) {
                                    queue.Enqueue(newWord);
                                    toVisit.Add(newWord);
                                }
                                predecessors[newWord].Add(currentWord);
                            }
                        }
                    }
                    
                    // 恢复原字符
                    chars[j] = originalChar;
                }
            }
        }
        
        return found;
    }
    
    private void DFS(string currentWord, string beginWord, Dictionary<string, List<string>> predecessors, List<string> path, IList<IList<string>> res) {
        if (currentWord == beginWord) {
            // 创建一个新的列表，并反转顺序
            List<string> newPath = new List<string>(path);
            newPath.Reverse();
            res.Add(newPath);
            return;
        }
        
        foreach (string predecessor in predecessors[currentWord]) {
            path.Add(predecessor);
            DFS(predecessor, beginWord, predecessors, path, res);
            path.RemoveAt(path.Count - 1);
        }
    }
}

Python 实现

from collections import defaultdict, deque

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        # 结果列表
        res = []
        
        # 将wordList转换为集合，便于快速查找
        word_set = set(wordList)
        
        # 如果endWord不在wordList中，直接返回空列表
        if endWord not in word_set:
            return res
        
        # 记录每个单词的前驱单词
        predecessors = defaultdict(list)
        
        # BFS找到最短路径
        if not self.bfs(beginWord, endWord, word_set, predecessors):
            return res
        
        # DFS回溯找到所有最短路径
        path = [endWord]
        self.dfs(endWord, beginWord, predecessors, path, res)
        
        return res
    
    def bfs(self, beginWord, endWord, word_set, predecessors):
        queue = deque([beginWord])
        visited = set([beginWord])
        to_visit = set([beginWord])
        
        found = False
        
        while queue and not found:
            visited.update(to_visit)
            to_visit = set()
            
            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:]
                        
                        # 如果新单词在word_set中
                        if new_word in word_set:
                            # 如果找到了endWord
                            if new_word == endWord:
                                found = True
                                predecessors[new_word].append(current_word)
                            # 如果新单词还没有被访问过
                            elif new_word not in visited:
                                # 如果新单词还没有在当前层被访问过
                                if new_word not in to_visit:
                                    queue.append(new_word)
                                    to_visit.add(new_word)
                                predecessors[new_word].append(current_word)
        
        return found
    
    def dfs(self, current_word, begin_word, predecessors, path, res):
        if current_word == begin_word:
            # 创建一个新的列表，并反转顺序
            res.append(path[::-1])
            return
        
        for predecessor in predecessors[current_word]:
            path.append(predecessor)
            self.dfs(predecessor, begin_word, predecessors, path, res)
            path.pop()

C++ 实现

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        // 结果列表
        vector<vector<string>> res;
        
        // 将wordList转换为unordered_set，便于快速查找
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        
        // 如果endWord不在wordList中，直接返回空列表
        if (wordSet.find(endWord) == wordSet.end()) {
            return res;
        }
        
        // 记录每个单词的前驱单词
        unordered_map<string, vector<string>> predecessors;
        
        // BFS找到最短路径
        if (!bfs(beginWord, endWord, wordSet, predecessors)) {
            return res;
        }
        
        // DFS回溯找到所有最短路径
        vector<string> path = {endWord};
        dfs(endWord, beginWord, predecessors, path, res);
        
        return res;
    }
    
private:
    bool bfs(string beginWord, string endWord, unordered_set<string>& wordSet, unordered_map<string, vector<string>>& predecessors) {
        queue<string> q;
        unordered_set<string> visited;
        unordered_set<string> toVisit;
        
        q.push(beginWord);
        toVisit.insert(beginWord);
        
        bool found = false;
        
        while (!q.empty() && !found) {
            visited.insert(toVisit.begin(), toVisit.end());
            toVisit.clear();
            
            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;
                        
                        // 如果新单词在wordSet中
                        if (wordSet.find(currentWord) != wordSet.end()) {
                            // 如果找到了endWord
                            if (currentWord == endWord) {
                                found = true;
                                predecessors[currentWord].push_back(currentWord);
                                currentWord[j] = originalChar;
                                predecessors[endWord].push_back(currentWord);
                                break;
                            }
                            // 如果新单词还没有被访问过
                            else if (visited.find(currentWord) == visited.end()) {
                                // 如果新单词还没有在当前层被访问过
                                if (toVisit.find(currentWord) == toVisit.end()) {
                                    q.push(currentWord);
                                    toVisit.insert(currentWord);
                                }
                                string temp = currentWord;
                                currentWord[j] = originalChar;
                                predecessors[temp].push_back(currentWord);
                                continue;
                            }
                        }
                        
                        // 恢复原字符
                        currentWord[j] = originalChar;
                    }
                    
                    if (found) break;
                }
                
                if (found) break;
            }
        }
        
        return found;
    }
    
    void dfs(string currentWord, string beginWord, unordered_map<string, vector<string>>& predecessors, vector<string>& path, vector<vector<string>>& res) {
        if (currentWord == beginWord) {
            // 创建一个新的列表，并反转顺序
            vector<string> newPath = path;
            reverse(newPath.begin(), newPath.end());
            res.push_back(newPath);
            return;
        }
        
        for (const string& predecessor : predecessors[currentWord]) {
            path.push_back(predecessor);
            dfs(predecessor, beginWord, predecessors, path, res);
            path.pop_back();
        }
    }
};

执行结果

C# 实现

• 执行用时：1256 ms
• 内存消耗：48.6 MB

Python 实现

• 执行用时：92 ms
• 内存消耗：17.2 MB

C++ 实现

• 执行用时：24 ms
• 内存消耗：13.5 MB

性能对比

语言	执行用时	内存消耗	特点
C#	1256 ms	48.6 MB	执行速度较慢，内存消耗较高
Python	92 ms	17.2 MB	执行速度适中，内存消耗适中
C++	24 ms	13.5 MB	执行速度最快，内存消耗最低

代码亮点

1. 🎯 使用BFS+DFS的组合策略，高效找出所有最短路径
2. 💡 使用哈希表记录前驱单词，避免重复搜索
3. 🔍 在BFS过程中巧妙处理层级关系，确保找到的是最短路径
4. 🎨 代码结构清晰，分为BFS和DFS两个独立函数，逻辑分明

常见错误分析

1. 🚫 没有正确处理单词的前驱关系，导致无法找到所有路径
2. 🚫 BFS实现不当，没有按层遍历，导致找到的不是最短路径
3. 🚫 没有正确处理已访问单词，导致死循环或重复访问
4. 🚫 没有检查endWord是否在wordList中，导致不必要的搜索

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
BFS + DFS	O(N * C^2 + a)	O(N * C + a)	实现相对简单，思路清晰	在单词数量大时效率较低
双向BFS + DFS	O(N * C^2 + a)	O(N * C + a)	搜索效率更高，尤其是在单词数量大时	实现复杂，需要处理两个方向的搜索
纯BFS（记录路径）	O(N * C^2 * a)	O(N * C * a)	不需要DFS回溯	空间复杂度高，需要存储所有可能的路径

相关题目

• LeetCode 127. 单词接龙 - 中等
• LeetCode 433. 最小基因变化 - 中等
• LeetCode 752. 打开转盘锁 - 中等
• LeetCode 1091. 二进制矩阵中的最短路径 - 中等
• LeetCode 1293. 网格中的最短路径 - 困难