LeetCode127. 单词接龙

力扣

解题思路: 像这种BFS类型的题都有类似的模板

更好的理解 ->  B站 : 花花酱

1.单向BFS

class Solution 
{
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {//hash表的查询效率最高 unordered_set<string> wordDict(wordList.begin(), wordList.end()); unordered_set<string> visited; //标记单词是否已经访问过，访问过的不再访问 visited.insert(beginWord); queue<string> q; //初始化队列 q.push(beginWord); int res = 1; while (!q.empty()){ int nextSize = q.size(); //每一步都要把队列中上一步添加的所有单词转换一遍 //最短的转换肯定在这些单词当中， 所有这些词的转换只能算一次转换//因为都是上一步转换出来的 while (nextSize--){ string curWord = q.front(); q.pop(); if(curWord == endWord)return res;for (int i = 0; i < curWord.size(); i++)//尝试转换当前单词的每一个位置 { string newWord = curWord; for (char ch = 'a'; ch <= 'z'; ch++)//每一个位置用26个字母分别替换 {newWord[i] = ch; //判断新的单词是否在词典中，且没有搜索过if (wordDict.find(newWord) != wordDict.end()&& visited.find(newWord) == visited.end()) {visited.insert(newWord); //标记已使用q.push(newWord); }} }}++res; //转换成功  }//转换不成功，返回0 return 0;}
};

2.双向BFS

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {//双向广度优先搜索unordered_set<string> dict(wordList.begin() , wordList.end());if(dict.find(endWord) == dict.end())return 0;// 分别用左边和右边扩散的哈希表代替单向 BFS 里的队列，它们在双向 BFS 的过程中交替使用unordered_set<string> q1{beginWord}; //从前向后搜索unordered_set<string> q2{endWord}; //从后向前搜索int len = beginWord.size();//执行双向 BFS，左右交替扩散的步数之和为所求int ans = 0;while(!q1.empty() && !q2.empty()){++ans;// 优先选择小的哈希表进行扩散，考虑到的情况更少if(q1.size() > q1.size())std::swap(q1,q2);unordered_set<string> q;//遍历原来哈希表中的单词 ，产生的新的序列保存在这里//这里遍历每一个节点的单词，然后修改其中一个字符，让他成为一个新的单词，//并查看这个新的单词在字典中是否存在，如果存在并且没有被访问过，就加入到队列中for(string str : q1){for(int i = 0 ; i < len ;++i){char ch = str[i];for(char ch = 'a' ; ch <= 'z' ;++ch){str[i] = ch;if (q2.find(str) != q2.end()) return ans + 1;if (dict.find(str) == dict.end()) continue;dict.erase(str);q.insert(str);}str[i] = ch;}}std::swap(q , q1);//将新的序列和老的序列交换}return  0 ;}
};