题目描述
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
- 如果不存在这样的转换序列，返回 0。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
题解
无向无权图中，每个单词作为节点，差距只有一个字母的两个单词之间连一条边。问题变成找到从起点到终点的最短路径，如果存在的话。因此可以使用广度优先搜索方法。
为了快速的找到这些相邻节点，我们对给定的 wordList 做一个预处理，将单词中的某个字母用 * 代替。这步预处理找出了单词表中所有单词改变某个字母后的通用状态，更方便也更快的找到相邻节点。否则，对于每个单词我们需要遍历整个字母表查看是否存在一个单词与它相差一个字母，这将花费很多时间。预处理操作在广度优先搜索之前高效的建立了邻接表。
如果使用两个同时进行的广搜可以有效地减少搜索空间。一边从 beginWord 开始，另一边从 endWord 开始。我们每次从两边各扩展一个节点，当发现某一时刻两边都访问了某一顶点时就停止搜索。这就是双向广度优先搜索，它可以可观地减少搜索空间大小，从而降低时间和空间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> dict(wordList.begin(), wordList.end());
if (dict.find(endWord) == dict.end() ) return 0;
unordered_set<string> beginSet, endSet, tmp, visited;
beginSet.insert(beginWord);
endSet.insert(endWord);
int len = 1;
while (!beginSet.empty() && !endSet.empty()){
if (beginSet.size() > endSet.size()){
tmp = beginSet;
beginSet = endSet;
endSet = tmp;
}
tmp.clear();
for ( string word : beginSet){
for (int i = 0; i < word.size(); i++){
char old = word[i];
for ( char c = 'a'; c <= 'z'; c++){
if ( old == c) continue;
word[i] = c;
if (endSet.find(word) != endSet.end()){
return len+1;
}
if (visited.find(word) == visited.end() && dict.find(word) != dict.end()){
tmp.insert(word);
visited.insert(word);
}
}
word[i] = old;
}
}
beginSet = tmp;
len++;
}
return 0;
}
};
作者：xu-zhou-geng
链接：https:
|