题目简介：
给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典中的单词。
说明:
- 如果不存在这样的转换序列，返回一个空列表。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
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"]
]
|
示例 2:
1
2
3
4
5
6
7
8
| 输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: []
解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。
|
思路：
讲真这题是真的难…看着官方题解懂了七七八八，但是还没吃透。
为了方便将每个单词设置一个id，设置了word -> id和id -> word的两个映射，方便后续的操作。
先将单词表中的单词加入这两个映射，若单词表中不存在结束单词，则说明无法通过转换达到，返回空即可。
然后开始构图，将每个单词看作一个结点，若两个单词不同字母数为1(题目给定单词均为相等长度，不用考虑长度的问题)，说明能互相转换，则在这两个结点之间添加两条有向边。
接下来设置一个队列开始广度优先搜索，队列中的每一个元素都是从起点开始，到某一个结点结束的路径。
将从队列拿出的当前元素记为now_path，若它的最后一个元素，即此路径的结束结点和我们所需要的结束单词相同，则此路径为答案路径之一，存入res中。
若不同，则依次循环此结束结点所连接的下一个结点，记为next。设置一个cost数组，cost[id]代表从起始单词出发，到id代表的单词时，需要转换的最少次数。
若刚才路径上的最后一个单词记为last_word，那么若cost[last_word] + 1 <= cost[next]，(相等也可以的目的是找到相同长度的路径)，则将next结点加入路径中，并压入队列。否则，便说明当前路径并不为最短路径(之前已经有更短的路径访问过这个结点)。这也说明了在队列中拿出的路径元素，若最后一个单词与目标结束单词相等，则此路径便为最短路径。
最后返回res即可。
tips:
- 在
bool check_transform(string &word1, string &word2)函数中，若参数不加&，便会超时，原因是因为C++不加&，是函数参数值传递，需要重新拷贝一份数据，所以慢。而加&是引用传递，用的还是原来在内存的变量，不需要花时间拷贝一份。
cost[last_word] + 1 <= cost[next]相当于 cost[last_word] + 1 == cost[next] || cost[next] == INT_MAX- 对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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
| class Solution {
public:
bool check_transform(string &word1, string &word2){
int difference = 0;
for(int i = 0; i < word1.length() && difference < 2; i++){
if(word1[i] != word2[i])
difference++;
}
return difference == 1;
}
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
unordered_map<string, int> wordId;
vector<string> idWord;
vector<vector<int>> edges;
int id = 0;
for(int i = 0; i < wordList.size(); i++){
if(!wordId.count(wordList[i])){
wordId[wordList[i]] = id++;
idWord.push_back(wordList[i]);
}
}
if(!wordId.count(endWord))
return {};
if(!wordId.count(beginWord)){
wordId[beginWord] = id++;
idWord.push_back(beginWord);
}
edges.resize(id);
for(int i = 0; i < idWord.size(); i++){
for(int j = i + 1; j < idWord.size(); j++){
if(check_transform(idWord[i], idWord[j])){
edges[i].push_back(j);
edges[j].push_back(i);
}
}
}
int endWord_id = wordId[endWord];
vector<vector<string>> res;
queue<vector<int>> q;
q.push(vector<int>{wordId[beginWord]});
vector<int> cost(id, INT_MAX);
cost[wordId[beginWord]] = 0;
while(!q.empty()){
vector<int> now_path = q.front();
q.pop();
int last_word_id = now_path.back();
if(last_word_id == endWord_id){
vector<string> temp;
for(int i = 0; i < now_path.size(); i++){
temp.push_back(idWord[now_path[i]]);
}
res.push_back(temp);
}
else{
for(int i = 0; i < edges[last_word_id].size(); i++){
int next = edges[last_word_id][i];
if(cost[last_word_id] + 1 <= cost[next]){
cost[next] = cost[last_word_id] + 1;
vector<int> temp(now_path.begin(), now_path.end());
temp.push_back(next);
q.push(temp);
}
}
}
}
return res;
}
};
|
