链接: https://leetcode-cn.com/problems/word-ladder-ii/description/
题意
给定一个起始字符串和一个终止字符串，以及一个单词表，求是否可以将起始字符串每次改一个字符，直到改成终止字符串，且所有中间的修改过程表示的字符串都可以在单词表里找到。
输出需要修改次数最少的所有更改方式
解法
本题的难度是Hard，难点在于搜索过程中的优化
我们可以将这道题抽象成一个图，每个单词就是图中的一个结点
如果两个字符串只有一个字母不同，则这两个结点之间有一条边相连
建图的过程使用广度优先搜索，在建完以后进行回溯找出所有的路径
在实现上也有一些难点和可以学习的地方，代码也做了详细的注释
例如使用一个数组标记是否入队，遍历整个队列的for循环处理
有一个重点是，需要将图建成一个有向图
由于是BFS，所以会将队列中所有元素全拿出来进行建图，为了不产生走回头路的情况
结点之间只会是单项边
如果一个结点已经被访问过了，它就会被从单词表中去除
为了查找的高效，将单词表转成set进行处理
有一些count, erase和find的操作也需要熟练
在找某个字符串所有的邻居时，除了遍历所有字符串以外，还可以替换单词中的每一个字符，在单词表大的情况下可以降低计算复杂度
BFS建图完成后回溯完成路径的匹配，这是针对这一题而言的
对于单词接龙这一题而言，由于其只需要找到最短的路径长度，所以在BFS过程中只要找到目标字符串就可以结束
代码
126 单词接龙II1
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
82class Solution {
public:
vector<vector<string>> ans; // 存储答案
map<string, vector<string>> graph; // 存储图
vector<string> curPath; // 存储当前路径
vector<string> findNeighbors(string& word, unordered_set<string>& wordList) {
vector<string> ret;
for (int i = 0; i < word.size(); i++) {
char oldChar = word[i]; // 替换每一个字符
for (char ch = 'a'; ch <= 'z'; ch++) {
if (ch == oldChar) {
continue;
}
word[i] = ch;
if (wordList.count(word)) {
ret.push_back(word);
}
}
word[i] = oldChar; // 修改回原单词
}
return ret;
}
void backtrack(string& nowWord, string& endWord) {
if (nowWord == endWord) { // 回溯寻找
ans.push_back(curPath);
return;
}
for (auto word: graph[nowWord]) {
curPath.push_back(word);
backtrack(word, endWord);
curPath.pop_back();
}
}
void bfs(string& beginWord, string& endWord, unordered_set<string>& wordList) {
queue<string> q;
// 将beginWord从单词表中去除
if (wordList.count(beginWord)) {
wordList.erase(wordList.find(beginWord));
}
map<string, int> isEnqueued;
q.push(beginWord);
isEnqueued[beginWord] = 1;
while(q.size()) {
vector<string> vis;
for (int i = q.size() - 1; i >= 0; i--) {
// 遍历队列的for处理
string word = q.front();
q.pop();
vector<string> ret = findNeighbors(word, wordList);
// 找出word的所有邻居
for (auto idx: ret) {
graph[word].push_back(idx); // 建图
vis.push_back(idx); // 节点标记访问
if (isEnqueued[idx] == 0) {
isEnqueued[idx] = 1;
q.push(idx); // 如果该单词未被加入队列则入队
}
}
}
for (auto word: vis) {
// 去除所有已经被访问到的元素 以防产生双向边
if (wordList.count(word)) {
// 学习从set中erase单词的写法
wordList.erase(wordList.find(word));
}
}
}
}
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> newWordList(wordList.begin(), wordList.end());
bfs(beginWord, endWord, newWordList);
curPath = {beginWord};
backtrack(beginWord, endWord);
return ans;
}
};