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"
,
5
. Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
思路:
字符串的花儿挺多,word ladder也是CC150 v5上的18.10题,乍一看无从下手,其实就是BFS求单源无权最短路径。
想要大set不超时,关键有几点:
1. 一边加新词进queue,一边从dict里remove掉
2. 直接寻找所有可能的OneEditWords判断是否在dict里面,每次都过一遍dict一个一个判断是否为OneEditWords会超时。我还有一个超时的方法,就是寻找所有可能的OneEditWords再建一个跟dict求交集,后来发现algoritm里的只支持两个有序集合很坑,需要先把unordered_set转化为vector排序,结果不言而喻。
3. 将<string, int > path并到访问队列qwords里去会跑得更快,反正这里不要求输出路径,这个可以做下优化
4. 将getOneEditWords这个函数并到ladderLength里头会跑得更快,不过我觉得可读性会降低
1 int ladderLength(string start, string end, unordered_set&dict) { 2 unordered_set ndict(dict);//最好不要修改输入参数 3 queue qwords;//BFS访问队列 4 unordered_map path;//记录到start的最短路径,其实可以并入qwords中 5 6 qwords.push(start); 7 path[start] = 1; 8 ndict.erase(start); 9 10 while(!qwords.empty()){11 start = qwords.front();12 qwords.pop();13 int len = path[start];14 for(string s :getOneEditWords(start)){ //边局部构建map,边处理15 if(ndict.find(s) == ndict.end()) continue;//一个一个判断dict中元素是否为OneEditWords会超时16 if(s == end) return len+1;17 qwords.push(s);18 path[s] = len+1;19 ndict.erase(s);//如果不erase访问过的元素会超时20 }21 }22 return 0; 23 } 24 25 vector getOneEditWords(string start){26 vector words;27 for(unsigned int i = 0; i < start.size(); i++){28 string word(start);29 for(char ch = 'a'; ch <= 'z'; ch++){30 if(ch != start[i]){31 word[i] = ch;32 words.push_back(word);33 }34 }35 }36 return words; 37 }