爱情也有好赖，决不能草率，我是愿意等待，哪怕青春不再
[问题描述]
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
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/109754.html原文链接：https://javaforall.net
