leetcode
leetcode 101 ~ 150
单词接龙 II

单词接龙 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] 的形式返回。

 

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

代码结果

运行时间: 28 ms, 内存: 16.4 MB

/*
思路：
1. 使用BFS来找到从beginWord到endWord的所有最短转换路径。
2. 使用Stream API来简化代码处理，如过滤、映射等。
*/
import java.util.*;
import java.util.stream.*;
 
public class SolutionStream {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) return Collections.emptyList();
        Queue<List<String>> queue = new LinkedList<>();
        queue.offer(Arrays.asList(beginWord));
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        List<List<String>> result = new ArrayList<>();
        boolean found = false;
        while (!queue.isEmpty() && !found) {
            int size = queue.size();
            Set<String> levelVisited = new HashSet<>();
            for (int i = 0; i < size; i++) {
                List<String> path = queue.poll();
                String lastWord = path.get(path.size() - 1);
                found |= processWord(queue, visited, wordSet, endWord, result, levelVisited, path, lastWord);
            }
            visited.addAll(levelVisited);
        }
        return result;
    }
 
    private boolean processWord(Queue<List<String>> queue, Set<String> visited, Set<String> wordSet, String endWord, List<List<String>> result, Set<String> levelVisited, List<String> path, String lastWord) {
        char[] chars = lastWord.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 nextWord = new String(chars);
                if (wordSet.contains(nextWord)) {
                    if (nextWord.equals(endWord)) {
                        path.add(nextWord);
                        result.add(new ArrayList<>(path));
                        path.remove(path.size() - 1);
                        return true;
                    } else if (!visited.contains(nextWord)) {
                        path.add(nextWord);
                        queue.offer(new ArrayList<>(path));
                        path.remove(path.size() - 1);
                        levelVisited.add(nextWord);
                    }
                }
            }
            chars[j] = original;
        }
        return false;
    }
}

解释

方法:

这道题的解题思路是使用广度优先搜索（BFS）来寻找最短转换序列。首先，将 beginWord 加入到 wordList 中。然后构建一个桶（buckets），将 wordList 中的每个单词的每个字母都替换为下划线 '_'，生成对应的通配词，再把原单词加到对应的通配词映射的列表中。接着进行 BFS 遍历，从 beginWord 开始，每次将当前单词的每个字母都替换为下划线，在对应桶中找到所有匹配的单词，如果该单词没有被遍历过，就加入到待遍历队列（toSeen）和已探测词列表（beFound）中，同时记录下该单词的前溯词到 preWords 中。直到找到 endWord 且完成当前层的遍历，就可以结束 BFS。最后，从 endWord 出发，使用列表推导式不断遍历 preWords，生成最短转换序列的结果。

时间复杂度:

O(n*l)

空间复杂度:

O(n^2)

代码细节讲解

🦆
在生成通配词的过程中，为什么选择将每个字母依次替换为下划线'_'，这种方法有什么特别的优势吗？
▷
将每个字母依次替换为下划线 '_' 的方法创建了一个有效的通配符表示，这有助于快速找出所有可能的单词转换，而不需要逐一比较每个单词。这种方法减少了比较次数，提高了查找效率。例如，对于单词 'dog'，通过生成 'd_g', '_og', 'do_' 等通配词，我们可以立即获取所有只在一个位置上不同的单词，这是寻找单词变换的关键步骤。此外，这种方式也使得桶中的数据结构（即通配词到单词的映射）容易构建和查询，从而加快了整个算法的执行速度。
🦆
在BFS遍历中，如果有多个单词可以转换至同一个单词，如何保证记录的是最短路径上的转换？
▷
在广度优先搜索（BFS）中，我们通过维护一个已探测词列表（beFound）和其对应的层级来确保记录最短路径。当通过某个单词首次达到另一个单词时，我们记录这个单词的层级。如果后续再次达到这个单词但层级更高，则不再更新，因为更高的层级意味着路径更长。这样，我们可以确保每次记录的都是通过最短路径达到该单词的转换。同时，在添加前溯词时，只有当当前单词的层级正好比前溯词的层级多一时，才将前溯词添加到列表中，这保证了只有最短路径上的转换被记录。
🦆
关于前溯词列表preWords的管理，当一个单词可以由多个其他单词转换而来时，怎样决定哪些前溯词应该被加入到preWords中？
▷
前溯词列表preWords的管理通过检查层级来进行。当我们在BFS中遇到一个可以由多个其他单词转换而来的单词时，我们会检查每个潜在的前溯词的层级。只有当前溯词的层级正好比当前单词的层级少一，这表明从前溯词到当前单词是最短路径上的直接转换，这时才会将这个前溯词加入到preWords中。这种方式确保了preWords中只存储对构建最短路径有直接帮助的单词。

相关问题

单词接龙

字典 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 <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • beginWord、endWord 和 wordList[i] 由小写英文字母组成
  • beginWord != endWord
  • wordList 中的所有字符串 互不相同
验证回文串单词接龙