在刚开始接触算法时，解过一道这样的题
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 transformed word must exist in the word list. Note that beginWord is not a transformed word. For example, Given: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log","cog"] As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5. |
第一次做这道题的时候水平还不够，第一个思路是直接遍历字典，判断仅有一字之差的词，取出，重新遍历，代码如下：
bool canChange(string a, string b){ int num=0; for(int i=0; i<a.length(); i++){ if(a[i]!=b[i]) num++; } if(num==1) return true; else return false; } int ladderLength(string beginWord, string endWord, vector<string>& wordList) { int num=0; string a=beginWord; vector<string> myList=wordList; int i=0; while(i<myList.size()){ if(canChange(a, myList[i])){ num++; a=myList[i]; if(myList[i]==endWord) return num; i=-1; } i++; } return 0; } |
测试：
int main() { string a="hit"; string b="dot"; vector<string> c={"lot","dog","hot","log","cog","dot"}; cout << ladderLength(a,b,c); } |
结果为0
错误出在我写的算法的逻辑上，我并没有考虑到重复遍历的结果，这样可能会出现
hit->hot->hit->hot的循环，导致结果为0
改进算法后使用BFS遍历每条路径：
其思路就是先把起点加到队列中, 然后每次将字典中与队首距离为1的字符串加进队列, 直到最后出队列的是终点字符串, 为确保终点字符串存在, 我们可以先在字典中加进去终点字符串.
而在本题中在寻找与一个字符串相距为1的的字典中另一个字符串时如果一个个遍历字典消耗时间比较多, 每次时间复杂度是O(n). 在单个字符串不是很长的情况下, 一个个查看改变一个字符然后在字典中查看是否存在效率要更高些, 其时间复杂度是O(k log n), 其中k为单个字符串长度, n为字典长度.
代码如下
class Solution { public: int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) { wordList.insert(endWord); queue<pair<string, int>> que; que.push(make_pair(beginWord, 1)); wordList.erase(wordList.find(beginWord)); while(!que.empty()) { auto val = que.front(); que.pop(); if(val.first == endWord) return val.second; for(int i =0; i< val.first.size(); i++) { string str = val.first; for(int j = 0; j < 26; j++) { str[i] = 'a'+j; if(wordList.count(str) == 1) { que.push(make_pair(str, val.second+1)); wordList.erase(str); } } } } return 0; } }; |
上文内容不用于商业目的，如涉及知识产权问题，请权利人联系博为峰小编(021-64471599-8017)，我们将立即处理。
