# 127 - Word Ladder

解法一 - BFS

這提要求的是最短路徑，所以顯然用 backtracking(DFS) 不太適合，因為有可能求得的路徑不是最短路徑，所以用 DFS 得先找過所有路徑，再最後比較。而我們又知道 BFS 就是專門用來求無向無權重圖的最短路徑，所以這題就是要用 BFS，然後看到 endWord 在第幾層。

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        // Preprocessing wordList to let lookup easier
        unordered_set<string> dict;
        for(auto w: wordList) {
            dict.insert(w);
        }

        // BFS preparation
        int res=1, len=beginWord.length();
        queue<string> todo;
        todo.push(beginWord);

        // Start BFS
        while(!todo.empty()) {
            res++; 

            // Search all descendants of this level
            int thisLevel = todo.size();
            for(int numInLevel=0; numInLevel < thisLevel; numInLevel++) {
                string cur = todo.front();
                todo.pop();

                for(int i=0; i<len; i++) {
                    string tmp = cur;
                    for(int j=0; j<26; j++) {
                        tmp[i] = (char)('a'+j);

                        if(tmp == cur) continue;
                        else {
                            if(dict.find(tmp)!=dict.end()) {
                                if(tmp == endWord) return res;

                                todo.push(tmp);
                                dict.erase(dict.find(tmp));
                            }
                        }
                    }
                }
            }
        }

        return 0;
    }
};