Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Note:
思考：参考http://blog.csdn.net/doc_sgl/article/details/13341405
|
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 |
class
Solution {public: vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) { result_.clear(); unordered_map<string, vector<string>> prevMap; for(auto
iter = dict.begin(); iter != dict.end(); ++iter) prevMap[*iter] = vector<string>(); vector<unordered_set<string>> candidates(2); int
current = 0; int
previous = 1; candidates[current].insert(start); while(true) { current = !current; previous = !previous; for
(auto
iter = candidates[previous].begin(); iter != candidates[previous].end(); ++iter) dict.erase(*iter); candidates[current].clear(); for(auto
iter = candidates[previous].begin(); iter != candidates[previous].end(); ++iter) { for(size_t
pos = 0; pos < iter->size(); ++pos) { string word = *iter; for(int
i = ‘a‘; i <= ‘z‘; ++i) { if(word[pos] == i)continue; word[pos] = i; if(dict.count(word) > 0) { prevMap[word].push_back(*iter); candidates[current].insert(word); } } } } if
(candidates[current].size() == 0) return
result_; if
(candidates[current].count(end)) break; } vector<string> path; GeneratePath(prevMap, path, end); return
result_; } private: void
GeneratePath(unordered_map<string, vector<string>> &prevMap, vector<string>& path, const
string& word) { if
(prevMap[word].size() == 0) { path.push_back(word); vector<string> curPath = path; reverse(curPath.begin(), curPath.end()); result_.push_back(curPath); path.pop_back(); return; } path.push_back(word); for
(auto
iter = prevMap[word].begin(); iter != prevMap[word].end(); ++iter) GeneratePath(prevMap, path, *iter); path.pop_back(); } vector<vector<string>> result_;}; |
[LeetCode]Word Ladder II,布布扣,bubuko.com
原文：http://www.cnblogs.com/Rosanna/p/3598389.html