1. 題目

給定兩個(gè)單詞（beginWord 和 endWord）和一個(gè)字典 wordList，找出所有從 beginWord 到 endWord 的最短轉(zhuǎn)換序列。

轉(zhuǎn)換需遵循如下規(guī)則：

• 每次轉(zhuǎn)換只能改變一個(gè)字母。
• 轉(zhuǎn)換過程中的中間單詞必須是字典中的單詞。

說明:
如果不存在這樣的轉(zhuǎn)換序列，返回一個(gè)空列表。
所有單詞具有相同的長(zhǎng)度。
所有單詞只由小寫字母組成。
字典中不存在重復(fù)的單詞。
你可以假設(shè) beginWord 和 endWord 是非空的，且二者不相同。

示例 1: 輸入: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] 輸出: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"] ]示例 2: 輸入: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] 輸出: [] 解釋: endWord "cog" 不在字典中，所以不存在符合要求的轉(zhuǎn)換序列。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/word-ladder-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

類似題目：
LeetCode 127. 單詞接龍（圖的BFS/雙向BFS）
程序員面試金典 - 面試題 17.22. 單詞轉(zhuǎn)換（BFS）

2. BFS解題

• 詳見注釋

class Solution { public:vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {vector<vector<string>> ans;unordered_set<string> wlist(wordList.begin(),wordList.end());unordered_set<string> words;//存放當(dāng)次被加入到路徑的單詞queue<vector<string>> q;//隊(duì)列里存放的是可行的路徑q.push({beginWord});words.insert(beginWord);int level = 1, minLevel = INT_MAX, n, i;vector<string> frontPath, newPath;string lastWordOfPath, newLastWord;char ch;while(!q.empty()){n = q.size();while(n--){frontPath = q.front();//vector<string>q.pop();//frontPath出隊(duì)if(frontPath.size() > level)//下一個(gè)level時(shí)進(jìn)入{for(string word:words) wlist.erase(word);//將上一個(gè)lv進(jìn)入路徑的單詞從集合中刪除words.clear();level = frontPath.size();//level+1if(level > minLevel) //如果level比最小的還大，沒必要進(jìn)行下去break;}lastWordOfPath = frontPath.back();for(i = 0; i < lastWordOfPath.size(); i++){ //根據(jù)最后一個(gè)單詞衍生新的單詞newLastWord = lastWordOfPath;for(ch = 'a'; ch <= 'z'; ch++){newLastWord[i] = ch;if(!wlist.count(newLastWord)) //新單詞不在集合中,下一個(gè)continue;words.insert(newLastWord);//在集合中，加入路徑，并記錄在wordsnewPath = frontPath;//vector<string>newPath.push_back(newLastWord);if(newLastWord == endWord){ans.push_back(newPath);minLevel = level;}elseq.push(newPath);}}}}return ans;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 126. 单词接龙 II（图的BFS）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。