本文主要是介绍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
中的所有单词 互不相同
二、解题思路
-
初始化:将
beginWord
添加到队列中,并设置其距离为0。初始化一个图graph
来存储每个单词的相邻单词列表,和一个距离表distance
来存储每个单词到beginWord
的距离。 -
广度优先搜索:当队列不为空时,进行BFS。每次从队列中取出一个单词,并尝试将其每个位置的字母替换为’a’到’z’中的其他字母,生成新的单词。如果这个新单词在字典
wordSet
中且没有被访问过,或者已经被访问过但距离更短,则将其添加到队列中,并更新其距离和父节点。 -
找到最短路径:如果在BFS过程中找到了
endWord
,则标记找到并停止BFS。 -
回溯找到所有路径:如果找到了
endWord
,则从endWord
开始回溯,通过父节点信息找到所有从beginWord
到endWord
的最短路径,并将这些路径添加到结果列表中。 -
返回结果:如果找到了至少一条路径,则返回这些路径;如果没有找到,则返回空列表。
这个算法确保了只有最短路径会被考虑,因为它在找到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<>();// 使用双向BFSMap<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在找到最短路径后会停止,回溯过程中只考虑最短路径,这也会降低实际的时间和空间复杂度。
五、总结知识点
-
广度优先搜索(BFS):这是一种图遍历算法,用于从起点开始搜索最近的节点。在这个问题中,我们使用BFS来找到从
beginWord
到endWord
的最短转换序列。 -
双向BFS:这是一种优化的BFS,从起点和终点同时进行搜索,直到两者相遇。这样可以减少搜索空间,提高效率。
-
图的表示:我们使用一个哈希表
graph
来表示图,其中键是单词,值是与其相邻的单词列表。 -
哈希集合
Set
:用于存储wordList
中的单词,以便快速判断一个单词是否在字典中。 -
队列
Queue
:用于在BFS中存储待访问的节点。 -
回溯算法:这是一种递归算法,用于从终点回溯到起点,找到所有可能的转换序列。
-
列表
List
和数组ArrayList
:用于存储路径和单词的邻居。 -
字符数组和字符串操作:在代码中,我们使用了字符数组来表示单词,并通过改变字符数组中的字符来生成新的单词。
-
Java中的
char
类型和字符遍历:代码中使用了char
类型来表示字母,并通过循环遍历a
到z
来尝试所有可能的字符替换。 -
Java中的
Map
和Set
的操作:代码中使用了Map
和Set
的containsKey
、put
、computeIfAbsent
等方法来进行图的操作和单词的查找。 -
Java中的
Collections
类:用于操作集合,如reverse
方法用于反转列表。 -
递归函数:
backtrack
函数是一个递归函数,用于回溯找到所有可能的转换序列。
以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。
这篇关于LeetCode题练习与总结:单词接龙Ⅱ--126的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!