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(!q[current].empty()){
            string 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) {
                            prevMap[end].insert(prev); // in case end can be not in dict
                            done=true;
                        } else 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(q[current].empty()) {
                if(done) break;
                current=next;
                next=!current;
            }
        }

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

    void printPrevRec(deque<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){
                vector<string> res1;
                for(auto it=res.rbegin(); it!=res.rend(); it++) {
                    res1.push_back(*it);
                }
                solutions.push_back(res1);
            } else {
                printPrevRec(res, start, pmap, solutions);
            }
            res.pop_back();
        }
    }
};