class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<string> word_path;
        vector<vector<int>> path_prev;
        vector<int> path_prev_0;
        vector<int> level;
        int flag = 0;
        word_path.push_back(beginWord);
        path_prev_0.push_back(-1);
        path_prev.push_back(path_prev_0);
        level.push_back(0);
        list<string> new_wordlist;
        for(int i = 0;i<wordList.size();i++)
            new_wordlist.push_back(wordList[i]);
        auto wordlist_iter = new_wordlist.begin();
        while(wordlist_iter!= new_wordlist.end())
        {
            if(*wordlist_iter == beginWord)
            {
                new_wordlist.erase(wordlist_iter); 
                break;
            }
            wordlist_iter++;
        }
        bool success = false;
        flag = 0;
        for(int clevel = 0;;clevel++)
        {
            int level_begin_flag = flag;
            while(true)
            {
                if(flag>=word_path.size()) break;
                if(level[flag] > clevel) break;
                string ori_word = word_path[flag];
                flag++;
                if(success) continue;
                wordlist_iter = new_wordlist.begin();
                while(wordlist_iter!= new_wordlist.end())
                {
                    int diff = sim(*wordlist_iter, ori_word);
                    if(diff==1){
                        vector<int> path_prev_0;
                        word_path.push_back(*wordlist_iter);
                        path_prev.push_back(path_prev_0);
                        level.push_back(clevel+1);
                        if(*wordlist_iter == endWord)
                        {
                            success = true;
                            break;
                        }
                        wordlist_iter =  new_wordlist.erase(wordlist_iter); 
                    }
                    else{
                        wordlist_iter++;
                    }
                }
            }
            // no new node found
            if(flag>=word_path.size()) break;
            //update path_prev
            for(int i = flag;i<word_path.size();i++)
            {
                for(int j = level_begin_flag;j<flag;j++){
                    //cout << word_path[i] << " vs " <<word_path[j] << " "<<sim(word_path[i], word_path[j])<< endl;
                    if(sim(word_path[i], word_path[j])==1)
                        path_prev[i].push_back(j);
                }
            }
            //for(int i = 0;i<word_path.size();i++)
            //    cout << word_path[i] << "["<< level[i]<< "] ";
            //cout<<endl;
            //cout<<"---------\n";
            if(success) break;
        }
        vector<vector<string>> sol;
        if(!success) return sol;
        vector<string> c_sol;
        dfs(sol,word_path,path_prev,c_sol, word_path.size()-1);
        return sol;
    }
    void dfs(vector<vector<string>> &sol, vector<string> &word_path, vector<vector<int>> &path_prev, vector<string> c_sol, int id){
        //cout<<id<<" :";
        //for(auto i : path_prev[id])
        //    cout<<i<<' ';
        //cout<<endl;
        c_sol.insert(c_sol.begin(),word_path[id]);
        if(id==0){
            sol.push_back(c_sol);
            return;
        }
        for(auto i : path_prev[id]){
            dfs(sol,word_path,path_prev,c_sol,i);
        }
    }
    int sim(string a, string b){
        int diff = 0;
        for(int i=0;i<a.size();i++){
            if(a[i] != b[i])
                diff++;
            if(diff==2)
                break;
        }
        return diff;
    }
};