###### tags: `LeetCode` `BFS` `Hard` `DFS` `Queue`
# LeetCode #126 [Word Ladder II](https://leetcode.com/problems/word-ladder-ii/)
### (Hard-真的難)

按字典 wordList 完成從單詞 beginWord 到單詞 endWord 轉化，一個表示此過程的 轉換序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 這樣的單詞序列，並滿足：

每對相鄰的單詞之間僅有單個字母不同。
轉換過程中的每個單詞 si（1 <= i <= k）必須是字典 wordList 中的單詞。注意，beginWord 不必是字典 wordList 中的單詞。
sk == endWord
給你兩個單詞 beginWord 和 endWord ，以及一個字典 wordList 。請你找出並返回所有從 beginWord 到 endWord 的 最短轉換序列 ，如果不存在這樣的轉換序列，返回一個空列表。每個序列都應該以單詞列表 [beginWord, s1, s2, ..., sk] 的形式返回。

---

與 [#127](https://hackmd.io/Cz2A4hKcT9SOkJn0QBEx7w)有些類似, 但差別在需要回傳全部的最短路徑, 而非找到最短路徑長後就能結束。

為了(1)找到最短路徑以及(2)找到所有最短路徑組合, 需要建立一個資料結構儲存節點的父子關係以及該點的層級(到達該點的最短路徑長), 兩者皆可用無序哈希表unordered_map儲存。

此外, 使用bool found紀錄是否完成路徑探索, 若已找到, 則該輪探索完後就可以停止探索了(因為即使後面的探索找到終點, 仍然不是最短路徑)。

BFS的探索方式大同小異, 但要注意的的是由於路徑上的字串可能會被多個路徑經過, 因此不能隨意修改, 需要複製字串(元)後, 修改複製的字串(元)進行BFS搜尋。

註1:由於steps[s]在經過BFS搜尋後, 必定儲存到s點的最小值, 因此, 只有步數差距與steps[s]為1的單字才有資格成為s的parent(才有資格成為最短路徑的其中一個節點)。

在建完parent表後, 再透過DFS往回建立最短路徑組合。 由endWord開始, 遍歷每一個parent直到找到beginWord, 此時將暫存數組tmp存入答案數組中ans, 此外, 由於遍歷順序是從endWord -> beginWord, 因此在存入答案數組時, 需使用反轉指標(rbegin(), rend())。

註2:dict的功用是避免插入重複的parents, 導致最後的答案有重複值。

---

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end());
        if(!dict.count(endWord))return {};
        dict.erase(beginWord);
        dict.erase(endWord);
        queue<string> q;
        unordered_map<string, int> steps;
        steps[beginWord]=1;
        unordered_map<string, vector<string>> parents;
        q.push(beginWord);
        const int l = beginWord.length();
        bool found = false;
        int step = 0;
        vector<vector<string>> ans;
        
        while(!q.empty()&&!found){
            ++step;
            for(int i=q.size();i>0;i--){
                const string str = q.front();q.pop();
                string s = str;
                for(int j = 0; j<l;j++){
                    const char c = s[j];
                    for(char k = 'a'; k<='z';k++){
                        if(k==c)continue;
                        s[j]=k;
                        if(s==endWord){
                            parents[s].push_back(str);
                            found = true;
                        }
                        else{
                            //註1
                            if(steps.count(s)&&step==steps.at(s)-1)
                            parents[s].push_back(str);
                        }
                        if(dict.count(s)){
                            dict.erase(s);
                            steps[s]=steps.at(str)+1;
                            parents[s].push_back(str);
                            q.push(s);
                        }
                    }
                    s[j]=c;
                }
            }
        }
        if(found){
            vector<string> tmp{endWord};
            dfs(endWord, beginWord, parents, tmp, ans);
        }
        return ans;
    }
    void dfs(const string& word, 
             const string& beginWord, 
             const unordered_map<string, vector<string>>& parents, 
             vector<string>& tmp, 
             vector<vector<string>>& ans){
        if(word==beginWord){
            ans.push_back(vector<string>(tmp.rbegin(), tmp.rend()));
            return;
        }
        for(auto s:parents.at(word)){
            tmp.push_back(s);
            dfs(s, beginWord, parents, tmp, ans);
            tmp.pop_back();
        }
    }
};