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:
思路：
字符串的花儿挺多，word ladder的话用BFS，想要大set不超时，关键有几点：
1. 一边加新词进queue，一边从dict里remove掉
2. 直接寻找所有可能的OneEditWords判断是否在dict里面，每次都过一遍dict一个一个判断是否为OneEditWords会超时。我还有一个超时的方法，就是寻找所有可能的OneEditWords再建一个unordered_set跟dict求交集，后来发现algoritm里的set_intersection只支持两个有序集合很坑，需要先把unordered_set转化为vector排序，结果不言而喻。
3. 将unordered_map<string, int > path并到访问队列qwords里去会跑得更快，反正这里不要求输出路径，这个可以做下优化
4. 将getOneEditWords这个函数并到ladderLength里头会跑得更快，不过我觉得可读性会降低
1 int ladderLength(string start, string end, unordered_set<string> &dict) { 2 unordered_set<string> ndict(dict);//最好不要修改输入参数 3 queue<string> qwords;//BFS访问队列 4 unordered_map<string, int > 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<string> getOneEditWords(string start){ 26 vector<string> 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 }
【题解】【字符串】【BFS】【Leetcode】Word Ladder
原文：http://www.cnblogs.com/wei-li/p/WordLadder.html