給定兩個單詞（beginWord 和 endWord）和一個字典幕随，找到從 beginWord 到 endWord 的最短轉換序列的長度殖熟。轉換需遵循如下規(guī)則：
1.每次轉換只能改變一個字母饼酿。
2.轉換過程中的中間單詞必須是字典中的單詞栏赴。
說明:
- 如果不存在這樣的轉換序列，返回 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" 不在字典中丹壕，所以無法進行轉換。
代碼
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> dict(wordList.begin(), wordList.end());
unordered_map<string, int> m;
queue<string> q;
m[beginWord] = 1;
q.push(beginWord);
while (!q.empty()) {
string word = q.front(); q.pop();
for (int i = 0; i < word.size(); ++i) {
string newWord = word;
for (char ch = 'a'; ch <= 'z'; ++ch) {
newWord[i] = ch;
if (dict.count(newWord) && newWord == endWord) return m[word] + 1;
if (dict.count(newWord) && !m.count(newWord)) {
q.push(newWord);
m[newWord] = m[word] + 1;
}
}
}
}
return 0;
}
};
