daily leetcode - word-ladder - !
题目地址
https://leetcode.com/problems/word-ladder/
题目描述
Given two words ( beginWord and endWord ), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord , such that:
- Only one letter can be changed at a time.
- Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
- You may assume no duplicates in the word list.
- You may assume beginWord and endWord are non-empty and are not the same.
Example 1:
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Example 2:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
思路
这道词句阶梯的问题给了我们一个单词字典,里面有一系列很相似的单词,然后给了一个起始单词和一个结束单词,每次变换只能改变一个单词,并且中间过程的单词都必须是单词字典中的单词,让我们求出最短的变化序列的长度。这道题还是挺有难度的,我当然是看了别人的解法才写出来的,这没啥的,从不会到完全掌握才是成长嘛~
当拿到题就懵逼的我们如何才能找到一个科学的探索解题的路径呢,那就是先别去管代码实现,如果让我们肉身解题该怎么做呢?让你将 'hit' 变为 'cog',那么我们发现这两个单词没有一个相同的字母,所以我们就尝试呗,博主会先将第一个 'h' 换成 'c',看看 'cit' 在不在字典中,发现不在,那么把第二个 'i' 换成 'o',看看 'hot' 在不在,发现在,完美!然后尝试 'cot' 或者 'hog',发现都不在,那么就比较麻烦了,我们没法快速的达到目标单词,需要一些中间状态,但我们怎么知道中间状态是什么。简单粗暴的方法就是brute force,遍历所有的情况,我们将起始单词的每一个字母都用26个字母来替换,比如起始单词 'hit' 就要替换为 'ait', 'bit', 'cit', .... 'yit', 'zit',将每个替换成的单词都在字典中查找一下,如果有的话,那么说明可能是潜在的路径,要保存下来。那么现在就有个问题,比如我们换到了 'hot' 的时候,此时发现在字典中存在,那么下一步我们是继续试接下来的 'hpt', 'hqt', 'hrt'... 还是直接从 'hot' 的首字母开始换 'aot', 'bot', 'cot' ... 这实际上就是BFS和DFS的区别,到底是广度优先,还是深度优先。讲到这里,不知道你有没有觉得这个跟什么很像?对了,跟迷宫遍历很像啊,你想啊,迷宫中每个点有上下左右四个方向可以走,而这里有26个字母,就是二十六个方向可以走,本质上没有啥区别啊!如果熟悉迷宫遍历的童鞋们应该知道,应该用BFS来求最短路径的长度,这也不难理解啊,DFS相当于一条路走到黑啊,你走的那条道不一定是最短的啊。而BFS相当于一个小圈慢慢的一层一层扩大,相当于往湖里扔个石头,一圈一圈扩大的水波纹那种感觉,当水波纹碰到湖上的树叶时,那么此时水圈的半径就是圆心到树叶的最短距离。脑海中有没有浮现出这个生动的场景呢?
明确了要用BFS,我们可以开始解题了,为了提到字典的查找效率,我们使用HashSet保存所有的单词。然后我们需要一个HashMap,来建立某条路径结尾单词和该路径长度之间的映射,并把起始单词映射为1。既然是BFS,我们需要一个队列queue,把起始单词排入队列中,开始队列的循环,取出队首词,然后对其每个位置上的字符,用26个字母进行替换,如果此时和结尾单词相同了,就可以返回取出词在哈希表中的值加一。如果替换词在字典中存在但在哈希表中不存在,则将替换词排入队列中,并在哈希表中的值映射为之前取出词加一。如果循环完成则返回0.
关键点解析
代码
解法一:
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> wordSet(wordList.begin(), wordList.end());
if (!wordSet.count(endWord)) return 0;
unordered_map<string, int> pathCnt{{{beginWord, 1}}};
queue<string> q{{beginWord}};
while (!q.empty()) {
string word = q.front(); q.pop();
for (int i = 0; i < word.size(); ++i) {
string newWord = word;
for (char ch = 'a'; ch <= 'z'; ++ch) {
newWord[i] = ch;
if (wordSet.count(newWord) && newWord == endWord) return pathCnt[word] + 1;
if (wordSet.count(newWord) && !pathCnt.count(newWord)) {
q.push(newWord);
pathCnt[newWord] = pathCnt[word] + 1;
}
}
}
}
return 0;
}
};
其实我们并不需要上面解法中的HashMap,由于BFS的遍历机制就是一层一层的扩大的,那么我们只要记住层数就行,然后在while循环中使用一个小trick,加一个for循环,表示遍历完当前队列中的个数后,层数就自增1,这样的话我们就省去了HashMap,而仅仅用一个变量res来记录层数即可,参见代码如下:
解法二:
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> wordSet(wordList.begin(), wordList.end());
if (!wordSet.count(endWord)) return 0;
queue<string> q{{beginWord}};
int res = 0;
while (!q.empty()) {
for (int k = q.size(); k > 0; --k) {
string word = q.front(); q.pop();
if (word == endWord) return res + 1;
for (int i = 0; i < word.size(); ++i) {
string newWord = word;
for (char ch = 'a'; ch <= 'z'; ++ch) {
newWord[i] = ch;
if (wordSet.count(newWord) && newWord != word) {
q.push(newWord);
wordSet.erase(newWord);
}
}
}
}
++res;
}
return 0;
}
};
本文参考自:
https://github.com/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode
思路2
拥有一个 beginWord
和一个 endWord
,分别表示图上的 start node
和 end node
。我们希望利用一些中间节点(单词)从 start node
到 end node
,中间节点是 wordList
给定的单词。我们对这个单词接龙每个步骤的唯一条件是相邻单词只可以改变一个字母。
我们将问题抽象在一个无向无权图中,每个单词作为节点,差距只有一个字母的两个单词之间连一条边。问题变成找到从起点到终点的最短路径,如果存在的话。因此可以使用广度优先搜索方法。
算法中最重要的步骤是找出相邻的节点,也就是只差一个字母的两个单词。为了快速的找到这些相邻节点,我们对给定的 wordList
做一个预处理,将单词中的某个字母用 *
代替。
这个预处理帮我们构造了一个单词变换的通用状态。例如:Dog ----> D*g <---- Dig
,Dog
和 Dig
都指向了一个通用状态 D*g
。
这步预处理找出了单词表中所有单词改变某个字母后的通用状态,并帮助我们更方便也更快的找到相邻节点。否则,对于每个单词我们需要遍历整个字母表查看是否存在一个单词与它相差一个字母,这将花费很多时间。预处理操作在广度优先搜索之前高效的建立了邻接表。
例如,在广搜时我们需要访问 Dug
的所有邻接点,我们可以先生成 Dug
的所有通用状态:
Dug => *ug
Dug => D*g
Dug => Du*
第二个变换 D*g
可以同时映射到 Dog
或者 Dig
,因为他们都有相同的通用状态。拥有相同的通用状态意味着两个单词只相差一个字母,他们的节点是相连的。
方法 1:广度优先搜索
想法
利用广度优先搜索搜索从 beginWord
到 endWord
的路径。
算法
-
对给定的
wordList
做预处理,找出所有的通用状态。将通用状态记录在字典中,键是通用状态,值是所有具有通用状态的单词。 -
将包含
beginWord
和1
的元组放入队列中,1
代表节点的层次。我们需要返回endWord
的层次也就是从beginWord
出发的最短距离。 -
为了防止出现环,使用访问数组记录。
-
当队列中有元素的时候,取出第一个元素,记为
current_word
。 -
找到
current_word
的所有通用状态,并检查这些通用状态是否存在其它单词的映射,这一步通过检查all_combo_dict
来实现。 -
从
all_combo_dict
获得的所有单词,都和current_word
共有一个通用状态,所以都和current_word
相连,因此将他们加入到队列中。 -
对于新获得的所有单词,向队列中加入元素
(word, level + 1)
其中level
是current_word
的层次。 -
最终当你到达期望的单词,对应的层次就是最短变换序列的长度。
标准广度优先搜索的终止条件就是找到结束单词。
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
// Since all words are of same length.
int L = beginWord.length();
// Dictionary to hold combination of words that can be formed,
// from any given word. By changing one letter at a time.
Map<String, List<String>> allComboDict = new HashMap<>();
wordList.forEach(
word -> {
for (int i = 0; i < L; i++) {
// Key is the generic word
// Value is a list of words which have the same intermediate generic word.
String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
List<String> transformations = allComboDict.getOrDefault(newWord, new ArrayList<>());
transformations.add(word);
allComboDict.put(newWord, transformations);
}
});
// Queue for BFS
Queue<Pair<String, Integer>> Q = new LinkedList<>();
Q.add(new Pair(beginWord, 1));
// Visited to make sure we don't repeat processing same word.
Map<String, Boolean> visited = new HashMap<>();
visited.put(beginWord, true);
while (!Q.isEmpty()) {
Pair<String, Integer> node = Q.remove();
String word = node.getKey();
int level = node.getValue();
for (int i = 0; i < L; i++) {
// Intermediate words for current word
String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
// Next states are all the words which share the same intermediate state.
for (String adjacentWord : allComboDict.getOrDefault(newWord, new ArrayList<>())) {
// If at any point if we find what we are looking for
// i.e. the end word - we can return with the answer.
if (adjacentWord.equals(endWord)) {
return level + 1;
}
// Otherwise, add it to the BFS Queue. Also mark it visited
if (!visited.containsKey(adjacentWord)) {
visited.put(adjacentWord, true);
Q.add(new Pair(adjacentWord, level + 1));
}
}
}
}
return 0;
}
}
复杂度分析
- 时间复杂度:
O(M \times N)O(M×N)
,其中MM
是单词的长度NN
是单词表中单词的总数。找到所有的变换需要对每个单词做MM
次操作。同时,最坏情况下广度优先搜索也要访问所有的NN
个单词。 - 空间复杂度:
O(M \times N)O(M×N)
,要在all_combo_dict
字典中记录每个单词的MM
个通用状态。访问数组的大小是NN
。广搜队列最坏情况下需要存储NN
个单词。
方法 2:双向广度优先搜索
想法
根据给定字典构造的图可能会很大,而广度优先搜索的搜索空间大小依赖于每层节点的分支数量。假如每个节点的分支数量相同,搜索空间会随着层数的增长指数级的增加。考虑一个简单的二叉树,每一层都是满二叉树的扩展,节点的数量会以 2 为底数呈指数增长。
如果使用两个同时进行的广搜可以有效地减少搜索空间。一边从 beginWord
开始,另一边从 endWord
开始。我们每次从两边各扩展一个节点,当发现某一时刻两边都访问了某一顶点时就停止搜索。这就是双向广度优先搜索,它可以可观地减少搜索空间大小,从而降低时间和空间复杂度。
算法
-
算法与之前描述的标准广搜方法相类似。
-
唯一的不同是我们从两个节点同时开始搜索,同时搜索的结束条件也有所变化。
-
我们现在有两个访问数组,分别记录从对应的起点是否已经访问了该节点。
-
如果我们发现一个节点被两个搜索同时访问,就结束搜索过程。因为我们找到了双向搜索的交点。过程如同从中间相遇而不是沿着搜索路径一直走。
双向搜索的结束条件是找到一个单词被两边搜索都访问过了。
- 最短变换序列的长度就是中间节点在两边的层次之和。因此,我们可以在访问数组中记录节点的层次。
class Solution {
private int L;
private Map<String, List<String>> allComboDict;
Solution() {
this.L = 0;
// Dictionary to hold combination of words that can be formed,
// from any given word. By changing one letter at a time.
this.allComboDict = new HashMap<>();
}
private int visitWordNode(
Queue<Pair<String, Integer>> Q,
Map<String, Integer> visited,
Map<String, Integer> othersVisited) {
Pair<String, Integer> node = Q.remove();
String word = node.getKey();
int level = node.getValue();
for (int i = 0; i < this.L; i++) {
// Intermediate words for current word
String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
// Next states are all the words which share the same intermediate state.
for (String adjacentWord : this.allComboDict.getOrDefault(newWord, new ArrayList<>())) {
// If at any point if we find what we are looking for
// i.e. the end word - we can return with the answer.
if (othersVisited.containsKey(adjacentWord)) {
return level + othersVisited.get(adjacentWord);
}
if (!visited.containsKey(adjacentWord)) {
// Save the level as the value of the dictionary, to save number of hops.
visited.put(adjacentWord, level + 1);
Q.add(new Pair(adjacentWord, level + 1));
}
}
}
return -1;
}
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (!wordList.contains(endWord)) {
return 0;
}
// Since all words are of same length.
this.L = beginWord.length();
wordList.forEach(
word -> {
for (int i = 0; i < L; i++) {
// Key is the generic word
// Value is a list of words which have the same intermediate generic word.
String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
List<String> transformations =
this.allComboDict.getOrDefault(newWord, new ArrayList<>());
transformations.add(word);
this.allComboDict.put(newWord, transformations);
}
});
// Queues for birdirectional BFS
// BFS starting from beginWord
Queue<Pair<String, Integer>> Q_begin = new LinkedList<>();
// BFS starting from endWord
Queue<Pair<String, Integer>> Q_end = new LinkedList<>();
Q_begin.add(new Pair(beginWord, 1));
Q_end.add(new Pair(endWord, 1));
// Visited to make sure we don't repeat processing same word.
Map<String, Integer> visitedBegin = new HashMap<>();
Map<String, Integer> visitedEnd = new HashMap<>();
visitedBegin.put(beginWord, 1);
visitedEnd.put(endWord, 1);
while (!Q_begin.isEmpty() && !Q_end.isEmpty()) {
// One hop from begin word
int ans = visitWordNode(Q_begin, visitedBegin, visitedEnd);
if (ans > -1) {
return ans;
}
// One hop from end word
ans = visitWordNode(Q_end, visitedEnd, visitedBegin);
if (ans > -1) {
return ans;
}
}
return 0;
}
}
复杂度分析
- 时间复杂度:
O(M \times N)O(M×N)
,其中MM
是单词的长度NN
是单词表中单词的总数。与单向搜索相同的是,找到所有的变换需要 M * NM∗N 次操作。但是搜索时间会被缩小一半,因为两个搜索会在中间某处相遇。 - 空间复杂度:
O(M \times N)O(M×N)
,要在all_combo_dict
字典中记录每个单词的MM
个通用状态,这与单向搜索相同。但是因为会在中间相遇,所以双向搜索的搜索空间变小。
- 作者:LeetCode
- 链接:https://leetcode-cn.com/problems/word-ladder/solution/dan-ci-jie-long-by-leetcode/
- 来源:力扣(LeetCode)
- 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。