class Solution {
public:
    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
        unordered_map<string, unordered_set<string>> prevMap;
        vector<vector<string>> solutions;
        deque<string> q[2];
        bool done=false;
        int current=0;
        int next=1;
        q[current].push_back(start);
        while(!done){
            while(!q[current].empty()){
                auto c=q[current].front();
                q[current].pop_front();
                string prev=c;
                for(int i=0;i<c.size();i++)
                    for(int k='a';k<='z';k++){
                        if(c[i]!=k){
                            char beforeChange=c[i];
                            c[i]=k;
                            if(c==end || dict.empty()) done=true;
                            if(dict.find(c)!=dict.end()){
                                if(prevMap.find(c)==prevMap.end()){
                                    q[next].push_back(c);
                                }
                                prevMap[c].insert(prev);
                            }
                            c[i]=beforeChange;
                        }
                    }

                for(auto s: q[next]){
                    dict.erase(s);
                }
            }
            if(done) break;
            current=next;
            next=!current;
        }

        if(done){
            vector<string>res;
            res.push_back(end);
            printPrevRec(res, start, prevMap, solutions);
        }
        return solutions;
    }

    void printPrevRec(vector<string>& res, string& start, unordered_map<string, unordered_set<string>>& pmap, vector<vector<string>>& solutions){
        for(auto e: pmap[res.back()]){
            res.push_back(e);
            if(e==start){
                solutions.push_back(res);
            } else {
                printPrevRec(res, start, pmap, solutions);
            }
            res.pop_back();
        }
    }
};