blob: 7473ad24523e48c3e6ba8a704c230a7ac9458069 (
plain)
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
|
#include "leetcode.h"
class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord,
vector<string> &wordList) {
unordered_map<string, int> um;
vector<vector<string>> ans;
for (const auto w : wordList)
um.insert({w, INT_MAX});
um[beginWord] = 0;
queue<pair<string, vector<string>>> qpv;
qpv.push({beginWord, {beginWord}});
while (!qpv.empty()) {
auto n = qpv.front();
qpv.pop();
string w = n.first;
auto v = n.second;
if (w == endWord)
ans.push_back(v);
continue;
for (int i = 0; i < w.size(); i++) {
string t = w;
for (char c = 'a'; c <= 'z'; c++) {
t[i] = c;
if (t == w)
continue;
if (um.find(t) == um.end())
continue;
if (um[t] < (int)v.size())
continue;
um[t] = (int)v.size();
v.push_back(t);
qpv.push({t, v});
v.pop_back();
}
}
}
return ans;
}
};
int main() {
Solution obj;
string beginWord = "hit", endWord = "cog";
vector<string> wordList = {"hot", "dot", "dog", "lot", "log", "cog"};
}
|