# 126 - Word Ladder II

解法一 - BFS 計算最短距離，再用 DFS 搜尋所有長度為最短距離的路徑

這個做法滿直觀的，首先用 #127 裡面的 BFS 做法找到最短距離，然後再用 DFS 找所有長度跟最短路徑一樣的路徑加到答案裡。

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

        // Do BFS to determine the distance
        vector<vector<string>> res;
        int dist = BFS(beginWord, endWord, dict);
        if(dist == 0) return res;

        // Do DFS to find the path
        vector<string> tmp = {beginWord};
        DFS(beginWord, endWord, dist-1, dict, res, tmp);

        return res;
    }


private:
    int BFS(string& beginWord, string& endWord, unordered_set<string> dict){
        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;
    }

    void DFS(string& beginWord, string& endWord, int dist, unordered_set<string>& dict, vector<vector<string>>& res, vector<string>& tmp) {        
        if(dist == 0 && tmp.back() == endWord) {
            res.push_back(tmp);
        }
        else if(dist < 0){
            return;
        }
        else {
            for(int i=0; i<beginWord.length(); i++) {
                for(int c=0; c<26; c++) {
                    string change = beginWord;
                    change[i] = (char)('a'+c);

                    if(change == beginWord || dict.find(change) == dict.end())
                        continue;

                    tmp.push_back(change);
                    dict.erase(dict.find(change));
                    DFS(change, endWord, dist-1, dict, res, tmp);
                    dict.insert(change);
                    tmp.pop_back();
                }
            }    
        }
    }
};

可惜這個方法實作出來會 TLE：

解法二 - BFS 建圖，DFS 搜索路徑

解法一會太慢主要是因為 DFS 搜索的空間太大，如果我們在 BFS 階段就先把 graph 建出來，就不用在 DFS 時浪費時間搜尋各種變化在不在 graph 中。

這個解法的程式碼對我來說還不太直觀，之後想學再回來。

解法三 - 對路徑做 BFS

主要是參考 這篇的解法，核心的想法是：

1. 對路徑進行 BFS（所以 queue 裡面存的是 vector<string>）。

2. 用 minLevel 來控制答案路徑的最長長度

3. 用 if (path.size() > level) { 來判斷是否已經進到下一層的 path

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        //It can be solved with standard BFS. The tricky idea is doing BFS of paths instead of words!
        //Then the queue becomes a queue of paths.
        vector<vector<string>> ans;
        queue<vector<string>> paths;
        unordered_set<string> dict(wordList.begin(), wordList.end());
        paths.push({beginWord});
        int level = 1;
        int minLevel = INT_MAX;

        //"visited" records all the visited nodes on this level
        //these words will never be visited again after this level 
        //and should be removed from wordList. This is guaranteed
        // by the shortest path.
        unordered_set<string> visited; 

        while (!paths.empty()) {
            vector<string> path = paths.front();
            paths.pop();

            // Use this condition to determine if we reach a new level
            if (path.size() > level) {
                //reach a new level
                for (string w : visited) dict.erase(w);
                visited.clear();
                if (path.size() > minLevel)
                    break;
                else
                    level = path.size();
            }

            string last = path.back();
            //find next words in wordList by changing
            //each element from 'a' to 'z'
            for (int i = 0; i < last.size(); ++i) {
                string news = last;
                for (char c = 'a'; c <= 'z'; ++c) {
                    news[i] = c;
                    if (dict.find(news) != dict.end()) {
                        //next word is in wordList
                        //append this word to path
                        //path will be reused in the loop
                        //so copy a new path
                        vector<string> newpath = path;
                        newpath.push_back(news);
                        visited.insert(news);
                        if (news == endWord) {
                            minLevel = level;
                            ans.push_back(newpath);
                        }
                        else
                            paths.push(newpath);
                    }
                }
            }
        }
        return ans;    
    }
};