基本上就是word ladder。直接来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
|
vector<string> transform(set<string> &dict, string from, string to) { vector<string> ans;
if
(from.length() != to.length()) {
return
ans;
}
queue<string> que;
map<string, string> prev_map;
que.push(from);
prev_map[from] = "";
while
(!que.empty()) {
string s = que.front();
que.pop();
if
(s == to) break;
for
(int
i = 0; i < s.length(); i++) {
char
tmp = s[i];
for
(char
c = ‘A‘; c <= ‘Z‘; c++) {
if
(tmp == c) continue;
s[i] = c;
if
(dict.find(s) != dict.end()
&& prev_map.find(s) == prev_map.end()) {
que.push(s);
prev_map[s] = s;
prev_map[s][i] = tmp;
}
}
s[i] = tmp;
}
}
if
(prev_map.find(to) == prev_map.end()) return
ans;
string last = to;
do
{
ans.push_back(last);
last = prev_map[last];
} while
(last != "");
for
(int
i = 0; i < ans.size() / 2; i++) {
int
k = ans.size() - i - 1;
string tmp = ans[i];
ans[i] = ans[k];
ans[k] = tmp;
}
return
ans;
} |