爱情也有好赖,决不能草率,我是愿意等待,哪怕青春不再
[问题描述]
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
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:
-
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
[解题思路]
BFS经典场景
1 int Solution::ladderLength(std::string start, std::string end, std::tr1::unordered_set<std::string> &dict) 2 { 3 std::queue<std::pair<std::string, int> > bfs; 4 std::tr1::unordered_set<std::string> path; 5 path.insert(start); 6 bfs.push(std::make_pair(start, 2)); 7 while(!bfs.empty()){ 8 std::string tmp = bfs.front().first; 9 int num = bfs.front().second; 10 for (int i = 0; i < tmp.length(); i ++){ 11 tmp = bfs.front().first; 12 for(char ti = 'a'; ti <= 'z'; ti ++){ 13 tmp[i] = ti; 14 if (tmp == end) 15 return num; 16 if (dict.find(tmp) != dict.end() && path.find(tmp) == path.end()){ 17 bfs.push(std::make_pair(tmp, num + 1)); 18 path.insert(tmp); 19 } 20 } 21 } 22 bfs.pop(); 23 } 24 return 0; 25 }
转载于:https://www.cnblogs.com/taizy/p/3910818.html
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/109754.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...