Leetcode: Word Ladder
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:
int ladderLength(string start, string end, unordered_set<string> &dict) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. if(start.size() != end.size()) return 0; if(start.empty() || end.empty())return 0; queue<string> path; path.push(start); int level = 1; int count = 1; dict.erase(start); while(dict.size() > 0 && !path.empty()) { string curword = path.front(); path.pop();count--; for(int i = 0; i < curword.size(); i++) { string tmp = curword; for(char j='a'; j<='z'; j++) { if(tmp[i]==j)continue; tmp[i] = j; if(tmp==end)return level+1; if(dict.find(tmp) != dict.end()) path.push(tmp); dict.erase(tmp); } } if(count==0) { count = path.size(); level++; } } return 0; }
补充:软件开发 , C++ ,