文章目錄

• • 1. 題目
  • 2. 圖的BFS解題
  • • 2.1 單向BFS
    • 2.2 雙向BFS ！厲害了

1. 題目

給定兩個單詞（beginWord 和 endWord）和一個字典，找到從 beginWord 到 endWord 的最短轉換序列的長度。
轉換需遵循如下規則：

• 每次轉換只能改變一個字母。
• 轉換過程中的中間單詞必須是字典中的單詞。

說明:
如果不存在這樣的轉換序列，返回 0。
所有單詞具有相同的長度。
所有單詞只由小寫字母組成。
字典中不存在重復的單詞。
你可以假設 beginWord 和 endWord 是非空的，且二者不相同。

示例 1: 輸入: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] 輸出: 5 解釋: 一個最短轉換序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",返回它的長度 5。示例 2: 輸入: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] 輸出: 0 解釋: endWord "cog" 不在字典中，所以無法進行轉換。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/word-ladder
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 圖的BFS解題

題目有點惡心的地方在于，beginWord不知道是不是在list內，需要判斷
類似題目：
程序員面試金典 - 面試題 17.22. 單詞轉換（BFS）
LeetCode 126. 單詞接龍 II（圖的BFS）

2.1 單向BFS

• 利用隊列進行BFS

class Solution { public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {int len = wordList.size(), i, k, n, lv = 0;unordered_map<string,int> m;bool visited[len] = {false};for(i = 0; i < len; ++i){m[wordList[i]] = i;if(wordList[i] == beginWord)visited[i] = true;}if(m.find(endWord) == m.end())return 0;queue<string> q;string str;q.push(beginWord);while(!q.empty()){lv++;n = q.size();while(n--){for(i = 0; i < beginWord.size(); ++i){//對每個單詞的每個字符進行改變str = q.front();for(k = 1; k <= 25; ++k){str[i] += 1;if(str[i] > 'z')str[i] = 'a';if(m.find(str) != m.end() && !visited[m[str]]){ //在集合中，且沒有訪問的q.push(str);visited[m[str]] = true;if(str == endWord)return lv+1;}}}q.pop();}}return 0;} };

2.2 雙向BFS ！厲害了

• 從起始和終點分別開始BFS，2個隊列
• visited 存儲int值，初始化為0，正向訪問了+1，反向訪問了+2，如果某個visited的值為3，說明都訪問到了（連通了）
• 每次選擇隊列較短的一端繼續BFS（減少隊列擴大的規模，提高效率）

class Solution { public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {int len = wordList.size(), wlen = beginWord.size(), i, k, n, n1, n2, flag, lv = 0;unordered_map<string,int> m;vector<int> visited(len,0);bool beginWordInList = false;for(i = 0; i < len; ++i){m[wordList[i]] = i;if(wordList[i] == beginWord)//判斷beginWord在List中否{visited[i] = 1;//beginWord正向訪問beginWordInList = true;}}if(!beginWordInList)//beginWord不在list中{visited.push_back(1);//添加起點正向訪問，值為1m[beginWord] = len;//哈希表添加}if(m.find(endWord) == m.end())return 0;queue<string> q1, q2;string str;q1.push(beginWord);q2.push(endWord);visited[m[endWord]] = 2;//終點反向訪問了，值為2while(!q1.empty() && !q2.empty()){lv++;//走的步數n1 = q1.size();n2 = q2.size();queue<string> &Q = n1<n2 ? q1 : q2;//Q是較短的隊列的引用flag = n1<n2 ? 1 : 2;//訪問后增加的值n = Q.size();while(n--){for(i = 0; i < wlen; ++i){str = Q.front();for(k = 1; k <= 25; ++k){str[i] += 1;if(str[i] > 'z')str[i] = 'a';if(m.find(str) != m.end() && visited[m[str]] != flag){ //不等于1說明正向沒有訪問，不等于2說明反向沒有訪問Q.push(str);visited[m[str]] += flag;if(visited[m[str]] == 3)//等于3說明，雙向訪問過，找到路徑return lv+1;}}}Q.pop();}}return 0;} };

總結

以上是生活随笔為你收集整理的LeetCode 127. 单词接龙（图的BFS/双向BFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。