Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot"
-> "dog" -> "cog",
return its length 5.
Note:
思考：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 |
class
Solution {public: int
ladderLength(string start, string end, unordered_set<string> &dict) { queue<pair<string,int>> q; unordered_set<string> visited; q.push(make_pair(start, 1)); visited.insert(start); while
(!q.empty()) { string curStr = q.front().first; int
curStep = q.front().second; q.pop(); for
(int i = 0; i < curStr.size(); ++i) { string tmp = curStr; for
(int j = 0; j < 26; ++j) { tmp[i] = j+‘a‘; if(tmp == end) return
curStep+1; if(visited.find(tmp) == visited.end() && dict.find(tmp) != dict.end()) { q.push(make_pair(tmp, curStep+1)); visited.insert(tmp); } } } } return
0; }}; |
[LeetCode]Word Ladder,布布扣,bubuko.com
原文：http://www.cnblogs.com/Rosanna/p/3598384.html