127 单词接龙
传送门：https://leetcode-cn.com/problems/minimum-absolute-difference-queries/
Problem
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：
- 序列中第一个单词是
beginWord 。
- 序列中最后一个单词是
endWord 。
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典
wordList 中的单词。
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。
示例 1
1
2
3
| 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
|
示例 2
1
2
3
| 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。
|
提示
1
2
3
4
5
6
7
| 1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小写英文字母组成
beginWord != endWord
wordList 中的所有字符串互不相同
|
bfs
可以看作最短路问题，这里的每个单词就是一种状态，可以看作一个点，如何两个单词只相差一个字母，那么这两个字母之间就存在一条边，求两个点之间的最短路。
首先，如果$endWord$不在$wordList$中，不可能存在一种转换序列，返回0；
标记$wordList$中单词是否访问可以用$map$，每次扩展考虑当前单词的每一位，每一位有25种替换方法，又1 <= beginWord.length <= 10，第一层就有25*10=250种，第二层有250*250=62500种，第三层…，但最多只有5000*250=1250000。
直到扩展到$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
| class Solution {
public:
string s,e;
unordered_map<string,bool> ump;
int bfs(){
queue<string> q;
unordered_map<string,int> d;
q.push(s);
d[s]=0;
while(!q.empty()){
string t=q.front();
q.pop();
if(t==e) return d[t];
int dis=d[t];
for(int i=0;i<t.size();i++){
for(char j='a';j<='z';j++){
if(j==t[i]) continue;
string tt=t.substr(0,i)+j+t.substr(i+1,t.size()-1-i);
if(ump[tt]){
if(d.count(tt)==0){
d[tt]=dis+1;
q.push(tt);
}
}
}
}
}
return -1;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
for(auto i:wordList){
ump[i]=true;
}
s=beginWord;
e=endWord;
if(!ump[endWord]) return 0;
if(bfs()==-1) return 0;
return bfs()+1;
}
};
|
双向bfs
为了解决$bfs$搜索空间爆炸的问题，加速查找，可以用双向$bfs$，从$beginWord$和$endWord$分别查找。
两个方向分别$bfs$，每次选择状态数量较少的队列来扩展，可以使两个队列元素数量分布平均，也为了加快遍历的速度。
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
| class Solution {
public:
unordered_map<string,bool> ump;
string s,e;
int bfs(){
queue<string> q1,q2;
unordered_map<string,int> d1,d2;
q1.push(s);
d1[s]=0;
q2.push(e);
d2[e]=0;
while(!q1.empty()&&!q2.empty()){
if(q1.size()<=q2.size()){
string t=q1.front();
q1.pop();
if(d2.count(t)!=0){
return d1[t]+d2[t];
}
for(int i=0;i<t.size();i++){
for(char j='a';j<='z';j++){
if(j!=t[i]){
string tt=t.substr(0,i)+j+t.substr(i+1,t.size()-1-i);
if(ump[tt]){
if(d1.count(tt)==0){
q1.push(tt);
d1[tt]=d1[t]+1;
}
}
}
}
}
}
else{
string t=q2.front();
q2.pop();
if(d1.count(t)!=0){
return d1[t]+d2[t];
}
for(int i=0;i<t.size();i++){
for(char j='a';j<='z';j++){
if(j!=t[i]){
string tt=t.substr(0,i)+j+t.substr(i+1,t.size()-1-i);
if(ump[tt]){
if(d2.count(tt)==0){
q2.push(tt);
d2[tt]=d2[t]+1;
}
}
}
}
}
}
}
return -1;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
for(auto i: wordList){
ump[i]=true;
}
if(!ump[endWord]) return 0;
s=beginWord;
e=endWord;
return bfs()+1;
}
};
|
计算双向$bfs$的时间复杂度：
记$wordList$长度为$n$，字符串长度为$m$，搜索的结果都会在$wordList$中出现过（不符合条件的剪枝，不入队），加上起点共$n+1$个，
最坏情况所有结点两两连通，$n$个结点进入队列，每个结点$n$条出边，时间复杂度$O(n^2)$，每次找出边时，时间复杂度$O(m)$，总时间复杂度$O(m*n^2)$。
