LeetCode题练习与总结：单词接龙Ⅱ--126

一、题目描述

按字典 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] 的形式返回。

示例 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 中的所有单词 互不相同

二、解题思路

1. 初始化：将beginWord添加到队列中，并设置其距离为0。初始化一个图graph来存储每个单词的相邻单词列表，和一个距离表distance来存储每个单词到beginWord的距离。

2. 广度优先搜索：当队列不为空时，进行BFS。每次从队列中取出一个单词，并尝试将其每个位置的字母替换为’a’到’z’中的其他字母，生成新的单词。如果这个新单词在字典wordSet中且没有被访问过，或者已经被访问过但距离更短，则将其添加到队列中，并更新其距离和父节点。

3. 找到最短路径：如果在BFS过程中找到了endWord，则标记找到并停止BFS。

4. 回溯找到所有路径：如果找到了endWord，则从endWord开始回溯，通过父节点信息找到所有从beginWord到endWord的最短路径，并将这些路径添加到结果列表中。

5. 返回结果：如果找到了至少一条路径，则返回这些路径；如果没有找到，则返回空列表。

这个算法确保了只有最短路径会被考虑，因为它在找到endWord后停止了BFS，并且在回溯时只考虑了最短路径上的单词。这样可以避免生成和存储非最短路径，从而节省内存并提高效率。

三、具体代码

import java.util.*;

public class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) return new ArrayList<>();

        // 使用双向BFS
        Map<String, List<String>> graph = new HashMap<>();
        Map<String, Integer> distance = new HashMap<>();
        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);
        distance.put(beginWord, 0);

        boolean found = false;
        while (!queue.isEmpty()) {
            int level = distance.get(queue.peek());
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String current = queue.poll();
                char[] chars = current.toCharArray();
                for (int j = 0; j < chars.length; j++) {
                    char original = chars[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == original) continue;
                        chars[j] = c;
                        String newWord = new String(chars);
                        if (distance.containsKey(newWord) && distance.get(newWord) == level + 1) {
                            graph.computeIfAbsent(newWord, k -> new ArrayList<>()).add(current);
                        } else if (!distance.containsKey(newWord) && wordSet.contains(newWord)) {
                            distance.put(newWord, level + 1);
                            queue.add(newWord);
                            graph.computeIfAbsent(newWord, k -> new ArrayList<>()).add(current);
                        }
                    }
                    chars[j] = original;
                }
            }
            if (distance.containsKey(endWord)) {
                found = true;
                break;
            }
        }

        // 如果没有找到endWord，返回空列表
        if (!found) return new ArrayList<>();

        // 回溯找到所有路径
        List<List<String>> result = new ArrayList<>();
        List<String> path = new ArrayList<>();
        path.add(endWord);
        backtrack(graph, endWord, beginWord, path, result);

        return result;
    }

    private void backtrack(Map<String, List<String>> graph, String current, String beginWord, List<String> path, List<List<String>> result) {
        if (current.equals(beginWord)) {
            Collections.reverse(path);
            result.add(new ArrayList<>(path));
            Collections.reverse(path);
            return;
        }
        if (!graph.containsKey(current)) return;
        for (String next : graph.get(current)) {
            path.add(next);
            backtrack(graph, next, beginWord, path, result);
            path.remove(path.size() - 1);
        }
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度：

• 构建图的时间复杂度：对于每个单词，我们需要检查其所有可能的邻居（即通过改变每个位置的字母），共有wordList.size()个单词，每个单词有wordLength个字母，因此时间复杂度为O(wordList.size() * wordLength * 26)，因为字母表有26个字母。
• BFS的时间复杂度：在最坏情况下，我们需要访问图中的每个节点，并且对于每个节点，我们可能需要检查其所有邻居。因此，时间复杂度为O(V + E)，其中V是节点数，E是边数。在这个问题中，V最大为wordList.size()，E最大为wordList.size() * wordLength * 26（每个单词都有可能与其他所有单词相连）。
• 回溯的时间复杂度：在最坏情况下，我们需要回溯所有从beginWord到endWord的路径。每条路径的长度为pathLength，因此时间复杂度为O(pathLength * numPaths)，其中numPaths是最短路径的数量。
• 综合以上，总的时间复杂度为O(wordList.size() * wordLength * 26 + wordList.size() * wordLength * 26 + pathLength * numPaths)。

2. 空间复杂度：

• 图的空间复杂度：我们需要存储每个单词的邻居列表，因此空间复杂度为O(wordList.size() * wordLength * 26)。
• BFS队列的空间复杂度：在队列中，我们最多可能存储所有的单词，因此空间复杂度为O(wordList.size())。
• 距离表和路径列表的空间复杂度：这两个数据结构的空间复杂度也是O(wordList.size())。
• 回溯过程中的路径列表空间复杂度：在回溯过程中，我们为每条路径维护一个列表，因此空间复杂度为O(pathLength * numPaths)。

在实际应用中，由于每个单词的邻居数量通常远小于26个，因此实际的时间和空间复杂度可能会低于上述分析的上限。此外，由于BFS在找到最短路径后会停止，回溯过程中只考虑最短路径，这也会降低实际的时间和空间复杂度。

五、总结知识点

1. 广度优先搜索（BFS）：这是一种图遍历算法，用于从起点开始搜索最近的节点。在这个问题中，我们使用BFS来找到从beginWord到endWord的最短转换序列。

2. 双向BFS：这是一种优化的BFS，从起点和终点同时进行搜索，直到两者相遇。这样可以减少搜索空间，提高效率。

3. 图的表示：我们使用一个哈希表graph来表示图，其中键是单词，值是与其相邻的单词列表。

4. 哈希集合Set：用于存储wordList中的单词，以便快速判断一个单词是否在字典中。

5. 队列Queue：用于在BFS中存储待访问的节点。

6. 回溯算法：这是一种递归算法，用于从终点回溯到起点，找到所有可能的转换序列。

7. 列表List和数组ArrayList：用于存储路径和单词的邻居。

8. 字符数组和字符串操作：在代码中，我们使用了字符数组来表示单词，并通过改变字符数组中的字符来生成新的单词。

9. Java中的char类型和字符遍历：代码中使用了char类型来表示字母，并通过循环遍历a到z来尝试所有可能的字符替换。

10. Java中的Map和Set的操作：代码中使用了Map和Set的containsKey、put、computeIfAbsent等方法来进行图的操作和单词的查找。

11. Java中的Collections类：用于操作集合，如reverse方法用于反转列表。

12. 递归函数：backtrack函数是一个递归函数，用于回溯找到所有可能的转换序列。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。