解題思路：

首先判斷wordList中是否有endWord，如果沒有，就返回0。

pathCount用來存儲beginWord轉(zhuǎn)換到某一個(gè)word所需的長度，有點(diǎn)類似于動態(tài)規(guī)劃中用于記錄狀態(tài)的矩陣。

整體程序是一個(gè)廣度優(yōu)先搜索的邏輯。主要關(guān)注隊(duì)列q。while中每一次的循環(huán)就相當(dāng)于遍歷了二叉樹的某一層。

在第一層中，q只有beginWord這一個(gè)字符串，第一次大循環(huán)中，將beginWord能通過改變一個(gè)字符而得到的word集合（word必須是在wordList中的字符串），每一次循環(huán)就更新pathCount。

最先遇到newWord == endWord時(shí)，就是在最高的一層抵達(dá)結(jié)束字符串，其長度就是最短的。

?

class Solution { public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string> wordSet(wordList.begin(), wordList.end());if(!wordSet.count(endWord)) return 0;//用pathCount記錄路徑，轉(zhuǎn)換到某一個(gè)字符串所需長度unordered_map<string, int> pathCount{{{beginWord, 1}}};queue<string> q{{beginWord}};while(!q.empty()){string word = q.front();q.pop();for(int i = 0; i < word.size(); i++){string newWord = word;for(char c = 'a'; c <= 'z'; c++){newWord[i] = c;if(wordSet.count(newWord) && newWord == endWord) return pathCount[word] + 1;if(wordSet.count(newWord) && !pathCount.count(newWord)){pathCount[newWord] = pathCount[word] + 1;q.push(newWord);}}}}return 0;} };

?

?

總結(jié)

以上是生活随笔為你收集整理的Leetcode 127. 单词接龙 解题思路及C++实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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