基本上就是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;} |
原文：http://www.cnblogs.com/lautsie/p/3526377.html