参考文章：http://blog.csdn.net/yutianzuijin/article/details/12887747
Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
Only one letter can be changed at a time Each intermediate word must exist in the word list For example,
Given: beginWord = “hit” endWord = “cog” wordList = [“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 i=0,n=Q.size(),i
class Solution { public: int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) { unordered_set<string> visit; // if(!canEnter(beginWord,wordList)) return 0; queue<string> Q; Q.push(beginWord); visit.insert(beginWord); int step=-1; while(!Q.empty()){ step++; //类似于层次遍历，求所有节点 for(int i=0,n=Q.size();i<n;i++){ string s=Q.front(); Q.pop(); //退出循环 if(s==endWord){ return step+1; } if(validNext(s,endWord)){ return step+2; } //将当前单词的每一位进行替换a-z,判断是否出现在set中 for(int j=0;j<s.size();j++){ string tp=s; for(char c='a';c<='z';c++){ if(c==tp[j]) continue; swap(c,tp[j]); //如果这个可以在表中找到,并且没有使用过 if(wordList.find(tp)!=wordList.end() && visit.find(tp)==visit.end()){ Q.push(tp); visit.insert(tp); } swap(c,tp[j]); } } //这种遍历set中所有元素的方法，存在很多 // for(auto iter=wordList.begin();iter!=wordList.end();iter++){ // string s=(string) *iter; // //如果这个s没有被使用过 // if(visit.find(s)==visit.end()){ // Q.push(s); // //标记上 // visit.insert(s); // } // } } } return 0; } //判断一个元素能否进入列表 bool canEnter(string s,unordered_set<string>& wordList){ //在set里面找 for(auto iter=wordList.begin();iter!=wordList.end();iter++){ string item=(string) *iter; if(validNext(s,item)) return true; } return false; } //判断两个字符串只有一个位不相同 bool validNext(string &s,string &target){ int diff=0; for(int i=0;i<s.size();i++){ if(s[i]!=target[i]){ diff++; if(diff>=2) return false; } } if(diff==1) return true; return false; } };