126. Word Ladder II

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        set<string> unvisited(wordList.begin(), wordList.end());
        queue<string> visit;
        vector<vector<string>> res;
        int step = 0;
        unordered_map<string, vector<string>> graph;

        visit.push(beginWord);
        unvisited.erase(beginWord);

        while(!visit.empty()) {
            step++;
            set<string> currLayer;
            while(!visit.empty()) {
                string curr = visit.front();
                string next = curr;
                visit.pop();
                for (int j = 0; j < curr.size(); j++) {
                    char tmp = next[j];
                    for (char k = 'a'; k <= 'z'; k++) {
                        next[j] = k;
                        if (unvisited.count(next)) {
                            currLayer.insert(next);
                            unvisited.erase(next);
                        }
                        if (currLayer.count(next))
                            graph[next].push_back(curr);
                    }
                    next[j] = tmp;
                }
            }
            for (string newWord : currLayer)
                visit.push(newWord);
        }

        // for (string word:wordList) 
        //     for (string next:graph[word])
        //         cout<<word<<' '<<next<<endl;
        vector<string> tmp;
        DFS(endWord, beginWord, {}, res, graph);
        return res;
    }
private:
    void DFS(string curr, string tar, vector<string> ladder, vector<vector<string>> &res, unordered_map<string, vector<string>> &graph) {
        ladder.insert(ladder.begin(), curr);
        if (curr == tar) {
            res.push_back(ladder);
            return;
        }
        for (string next : graph[curr])
            DFS(next, tar, ladder, res, graph);
    }
};