Hard

题目描述

单词的变换序列是指从单词 beginWord 开始，每次只改变一个字母，最终到达单词 endWord 所经过的序列。

变换过程中的中间单词必须是字典 wordList 中的单词（注意：beginWord 不需要在字典中）。

给你两个单词 beginWord 和 endWord 和一个字典 wordList，找到从 beginWord 到 endWord 的最短变换序列的数目。

示例 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回溯构造所有路径。

算法步骤：

  1. BFS阶段：从起始单词开始，逐层搜索，直到找到目标单词或搜索完毕

    • 使用队列存储当前层的所有单词
    • 对每个单词，尝试改变每个位置的字母，找到字典中存在的邻接单词
    • 如果邻接单词是目标单词，记录找到的层数
    • 用哈希表记录每个单词的所有前驱单词，用于后续路径重构

  2. 路径重构阶段：从目标单词开始，使用DFS回溯所有可能的路径

    • 从endWord开始，通过前驱关系向前追溯到beginWord
    • 每找到一条完整路径就加入结果集

  3. 优化细节：

    • 使用set快速查找单词是否在字典中
    • 在BFS过程中及时删除已访问的单词，避免重复访问
    • 用层序遍历确保找到的是最短路径

推荐解法：BFS + DFS的组合方法，时间复杂度相对较优，实现清晰。

代码实现

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        vector<vector<string>> result;
        
        if (wordSet.find(endWord) == wordSet.end()) return result;
        
        unordered_map<string, vector<string>> neighbors;
        unordered_set<string> visited;
        queue<string> q;
        
        q.push(beginWord);
        visited.insert(beginWord);
        bool found = false;
        
        while (!q.empty() && !found) {
            unordered_set<string> currentLevel;
            int size = q.size();
            
            for (int i = 0; i < size; i++) {
                string word = q.front();
                q.pop();
                
                for (int j = 0; j < word.length(); j++) {
                    char originalChar = word[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == originalChar) continue;
                        word[j] = c;
                        
                        if (wordSet.find(word) != wordSet.end() && visited.find(word) == visited.end()) {
                            if (word == endWord) found = true;
                            neighbors[word].push_back(string(1, originalChar) + to_string(j));
                            currentLevel.insert(word);
                        }
                    }
                    word[j] = originalChar;
                }
            }
            
            for (const string& word : currentLevel) {
                visited.insert(word);
                q.push(word);
            }
        }
        
        if (!found) return result;
        
        vector<string> path = {endWord};
        dfs(beginWord, endWord, neighbors, path, result);
        return result;
    }
    
private:
    void dfs(const string& beginWord, const string& word, unordered_map<string, vector<string>>& neighbors, vector<string>& path, vector<vector<string>>& result) {
        if (word == beginWord) {
            result.push_back(vector<string>(path.rbegin(), path.rend()));
            return;
        }
        
        for (const string& neighbor : neighbors[word]) {
            path.push_back(neighbor);
            dfs(beginWord, neighbor, neighbors, path, result);
            path.pop_back();
        }
    }
};

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        if endWord not in wordList:
            return []
        
        wordSet = set(wordList)
        neighbors = defaultdict(list)
        visited = set()
        queue = deque([beginWord])
        visited.add(beginWord)
        found = False
        
        while queue and not found:
            current_level = set()
            for _ in range(len(queue)):
                word = queue.popleft()
                
                for i in range(len(word)):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        if c == word[i]:
                            continue
                        new_word = word[:i] + c + word[i+1:]
                        
                        if new_word in wordSet and new_word not in visited:
                            if new_word == endWord:
                                found = True
                            neighbors[new_word].append(word)
                            current_level.add(new_word)
            
            visited.update(current_level)
            queue.extend(current_level)
        
        if not found:
            return []
        
        result = []
        self.dfs(beginWord, endWord, neighbors, [endWord], result)
        return result
    
    def dfs(self, beginWord, word, neighbors, path, result):
        if word == beginWord:
            result.append(path[::-1])
            return
        
        for neighbor in neighbors[word]:
            path.append(neighbor)
            self.dfs(beginWord, neighbor, neighbors, path, result)
            path.pop()

public class Solution {
    public IList<IList<string>> FindLadders(string beginWord, string endWord, IList<string> wordList) {
        var result = new List<IList<string>>();
        var wordSet = new HashSet<string>(wordList);
        
        if (!wordSet.Contains(endWord)) return result;
        
        var neighbors = new Dictionary<string, List<string>>();
        var visited = new HashSet<string>();
        var queue = new Queue<string>();
        
        queue.Enqueue(beginWord);
        visited.Add(beginWord);
        bool found = false;
        
        while (queue.Count > 0 && !found) {
            var currentLevel = new HashSet<string>();
            int size = queue.Count;
            
            for (int i = 0; i < size; i++) {
                string word = queue.Dequeue();
                
                for (int j = 0; j < word.Length; j++) {
                    char originalChar = word[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == originalChar) continue;
                        
                        var newWord = word.Substring(0, j) + c + word.Substring(j + 1);
                        
                        if (wordSet.Contains(newWord) && !visited.Contains(newWord)) {
                            if (newWord == endWord) found = true;
                            
                            if (!neighbors.ContainsKey(newWord)) {
                                neighbors[newWord] = new List<string>();
                            }
                            neighbors[newWord].Add(word);
                            currentLevel.Add(newWord);
                        }
                    }
                }
            }
            
            foreach (string word in currentLevel) {
                visited.Add(word);
                queue.Enqueue(word);
            }
        }
        
        if (!found) return result;
        
        var path = new List<string> { endWord };
        DFS(beginWord, endWord, neighbors, path, result);
        return result;
    }
    
    private void DFS(string beginWord, string word, Dictionary<string, List<string>> neighbors, List<string> path, IList<IList<string>> result) {
        if (word == beginWord) {
            var reversedPath = new List<string>(path);
            reversedPath.Reverse();
            result.Add(reversedPath);
            return;
        }
        
        if (neighbors.ContainsKey(word)) {
            foreach (string neighbor in neighbors[word]) {
                path.Add(neighbor);
                DFS(beginWord, neighbor, neighbors, path, result);
                path.RemoveAt(path.Count - 1);
            }
        }
    }
}

var findLadders = function(beginWord, endWord, wordList) {
    const wordSet = new Set(wordList);
    if (!wordSet.has(endWord)) return [];
    
    const graph = new Map();
    const queue = [beginWord];
    const visited = new Set([beginWord]);
    let found = false;
    
    // Build adjacency graph using BFS
    while (queue.length && !found) {
        const levelVisited = new Set();
        const levelSize = queue.length;
        
        for (let i = 0; i < levelSize; i++) {
            const word = queue.shift();
            
            for (let j = 0; j < word.length; j++) {
                for (let c = 97; c <= 122; c++) {
                    const char = String.fromCharCode(c);
                    if (char === word[j]) continue;
                    
                    const newWord = word.slice(0, j) + char + word.slice(j + 1);
                    
                    if (wordSet.has(newWord) && !visited.has(newWord)) {
                        if (!graph.has(word)) graph.set(word, []);
                        graph.get(word).push(newWord);
                        
                        if (newWord === endWord) {
                            found = true;
                        }
                        
                        if (!levelVisited.has(newWord)) {
                            levelVisited.add(newWord);
                            queue.push(newWord);
                        }
                    }
                }
            }
        }
        
        for (const word of levelVisited) {
            visited.add(word);
        }
    }
    
    // DFS to find all paths
    const result = [];
    
    function dfs(word, path) {
        if (word === endWord) {
            result.push([...path]);
            return;
        }
        
        if (graph.has(word)) {
            for (const neighbor of graph.get(word)) {
                path.push(neighbor);
                dfs(neighbor, path);
                path.pop();
            }
        }
    }
    
    dfs(beginWord, [beginWord]);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(N × M²)，其中 N 是单词列表长度，M 是单词长度。BFS 需要 O(N × M) 检查每个单词的邻居，DFS 构造路径的复杂度取决于路径数量
空间复杂度O(N × M) 用于存储邻接关系和访问记录，额外的递归栈空间为路径长度

相关题目