【題目描述】
給定兩個單詞（beginWord 和 endWord）和一個字典偿警，找到從 beginWord 到 endWord 的最短轉(zhuǎn)換序列的長度。轉(zhuǎn)換需遵循如下規(guī)則：

每次轉(zhuǎn)換只能改變一個字母盒使。
轉(zhuǎn)換過程中的中間單詞必須是字典中的單詞七嫌。
說明:

如果不存在這樣的轉(zhuǎn)換序列，返回 0英妓。
所有單詞具有相同的長度。
所有單詞只由小寫字母組成辑畦。
字典中不存在重復(fù)的單詞。
你可以假設(shè) beginWord 和 endWord 是非空的纯出，且二者不相同暂筝。

示例 1:

輸入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

輸出: 5

解釋: 一個最短轉(zhuǎn)換序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
返回它的長度 5硬贯。

【思路分析】
BFS

1. 初始化將beginWord加入到queue中澄成，然后一次性pop出queue中所有的單詞，將其相鄰的單詞加入queue中
2. 如何找到相鄰單詞 - 暴力枚舉 對于單詞的每一位墨状，將它換為'a'-'z'。如果變更后的單詞在wordSet中列赎，則將其加入queue镐确。 是target則返回。不是wordSet則pass源葫。
3. 由于求最短路徑，一個word只能用一次嚷狞， 所以每次把單詞加入Queue的時(shí)候把該單詞從Queue中刪掉

【坑】

1. 注意題意荣堰，這里返回的是鏈表的長度振坚，不是需要改變的步驟
2. 對一個單詞修改循環(huán)后，要記得還原回原來的 --- 開始修改遍歷前用變量保存本來這個位置的字母

代碼

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    // create wordlist set
    unordered_set<string> wordSet;
    for (int i = 0; i < wordList.size(); ++i) {
        wordSet.insert(wordList[i]);
    }

    queue<string> q;
    int step = 0;

    if (!wordSet.count(endWord)) return 0;
    if (wordSet.count(beginWord)) {
        wordSet.erase(beginWord);
    }

    q.push(beginWord);
    while (!q.empty()) {
        step++;
        int size = q.size();
        while (size > 0) {
            string cur = q.front();
            q.pop();
            size--;
            for (int i = 0; i < cur.size(); i++) {
                char c = cur[i];
                for (char z = 'a'; z <= 'z'; z++) {
                    cur[i] = z;
                    if (cur == endWord) return step + 1;
                    else if (wordSet.count(cur)) {
                        wordSet.erase(cur);
                        //cout << "step: " << step << endl;
                        //cout << cur << endl;
                        //cout << "-----------" << endl;
                        q.push(cur);
                    }
                }
                //back the start state 
                cur[i] = c;   
            }
        }

    }
    return 0;
}