###### tags: `LeetCode` `BFS` `Hard` `String` `Queue`
# LeetCode #127 [Word Ladder](https://leetcode.com/problems/word-ladder/)
### (Hard)

字典 wordList 中從單詞 beginWord 和 endWord 的 轉換序列 是一個按下述規格形成的序列：

* 序列中第一個單詞是 beginWord 。
* 序列中最後一個單詞是 endWord 。
* 每次轉換只能改變一個字母。
* 轉換過程中的中間單詞必須是字典 wordList 中的單詞。

給你兩個單詞 beginWord 和 endWord 和一個字典 wordList ，找到從 beginWord 到 endWord 的 最短轉換序列 中的 單詞數目 。如果不存在這樣的轉換序列，返回 0。

---
先用unordered_set dict儲存wordList, 消除重複字串。

使用Queue, 先存入起始字串, 並把單詞數目設為1。

讀取Queue的第一個字串, 將其從dict裡刪除, 並針對每一個字元進行a到z的替換, 並確認dict是否存在替換後的字串, 若是, 則將其push到佇列中, 這些是現在字串在替換一個字元後可變成的字串, 在每一輪結束後, 將單詞數目+1。

如此循環直到替換的字串等同於endWord, 此時回傳單詞數目(beginWord需轉換幾次才能變成endWord)。

注意, 替換字元( word[i] )後須將字串回復成原本的樣子, 再進行下一個字元( word[i+1] )的替換。

( Queue常用於BFS搜尋? )

---

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end());
        queue<string> todo;
        todo.push(beginWord);
        int ladder = 1;
        while(!todo.empty()){
            for (int i = todo.size();i>0;i--){
                string word = todo.front();todo.pop();
                if(word==endWord)return ladder;
                dict.erase(word);
                for(int j=0;j<word.size();j++){
                    char c= word[j];
                    for(int k=0;k<26;k++){
                        word[j]='a' + k;
                        if(dict.find(word)!=dict.end())todo.push(word);
                    }
                    word[j]=c;
                }
            }
            ladder++;
        }
        return 0;
    }
};