题面
给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：
每次转换只能改变一个字母。
转换后得到的单词必须是字典中的单词。
说明:
- 如果不存在这样的转换序列，返回一个空列表。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
样例
1
2
3
4
5
6
7
8
9
10
| 输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出:
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
|
1
2
3
4
5
6
7
8
| 输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: []
解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。
|
思路
根据题意先将单词表构成一个无向图，然后bfs搜索路径。
这里注意，因为要求返回全部最短路径，所以bfs的队列中单纯的存节点行不通（Maybe可以吧）。
这里我们存路径，也就是从起点到这个点的路径，其他的和普通bfs没什么两样。
另外就是时间卡的有点紧，在构图的时候没有那句if(tmp > 1) break;就超时了？？找个时间优化一下算法。
( 这个题确实有点让人头大，还是太菜了
代码
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
| vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
int n, len, beg, end;
unordered_map<string, int> wti;
vector<vector<int>> G;
vector<string> words;
n = wordList.size(); if(n == 0) return {};
len = wordList[0].size();
words = wordList;
for(int i = 0; i < n; i++) {
wti[words[i]] = i;
}
if(!wti.count(endWord)) return {};
if(!wti.count(beginWord)) { words.push_back(beginWord); wti[beginWord] = n++; }
beg = wti[beginWord];
end = wti[endWord];
G.resize(n);
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
int tmp = 0;
for(int k = 0; k < len; k++) {
if(words[i][k] != words[j][k]) tmp++;
if(tmp > 1) break;
}
if(tmp == 1) {
G[i].push_back(j);
G[j].push_back(i);
}
}
}
vector<vector<string>> ans;
vector<int> dis(n, 0x3f3f3f);
dis[beg] = 0;
queue<vector<string>> q;
q.push({beginWord});
while(!q.empty()) {
vector<string> path = q.front(); q.pop();
int u = wti[path.back()];
if(u == end) {
ans.push_back(path);
}
else {
for(int v : G[u]) {
if(dis[u] + 1 <= dis[v]) {
vector<string> tmp = path;
tmp.push_back(words[v]);
q.push(tmp);
dis[v] = dis[u] + 1;
}
}
}
}
return ans;
}
|