<p>A <strong>transformation sequence</strong> from word <code>beginWord</code> to word <code>endWord</code> using a dictionary <code>wordList</code> is a sequence of words <code>beginWord -&gt; s<sub>1</sub> -&gt; s<sub>2</sub> -&gt; ... -&gt; s<sub>k</sub></code> such that:</p>

<ul>
	<li>Every adjacent pair of words differs by a single letter.</li>
	<li>Every <code>s<sub>i</sub></code> for <code>1 &lt;= i &lt;= k</code> is in <code>wordList</code>. Note that <code>beginWord</code> does not need to be in <code>wordList</code>.</li>
	<li><code>s<sub>k</sub> == endWord</code></li>
</ul>

<p>Given two words, <code>beginWord</code> and <code>endWord</code>, and a dictionary <code>wordList</code>, return <em>all the <strong>shortest transformation sequences</strong> from</em> <code>beginWord</code> <em>to</em> <code>endWord</code><em>, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words </em><code>[beginWord, s<sub>1</sub>, s<sub>2</sub>, ..., s<sub>k</sub>]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> beginWord = &quot;hit&quot;, endWord = &quot;cog&quot;, wordList = [&quot;hot&quot;,&quot;dot&quot;,&quot;dog&quot;,&quot;lot&quot;,&quot;log&quot;,&quot;cog&quot;]
<strong>Output:</strong> [[&quot;hit&quot;,&quot;hot&quot;,&quot;dot&quot;,&quot;dog&quot;,&quot;cog&quot;],[&quot;hit&quot;,&quot;hot&quot;,&quot;lot&quot;,&quot;log&quot;,&quot;cog&quot;]]
<strong>Explanation:</strong>&nbsp;There are 2 shortest transformation sequences:
&quot;hit&quot; -&gt; &quot;hot&quot; -&gt; &quot;dot&quot; -&gt; &quot;dog&quot; -&gt; &quot;cog&quot;
&quot;hit&quot; -&gt; &quot;hot&quot; -&gt; &quot;lot&quot; -&gt; &quot;log&quot; -&gt; &quot;cog&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> beginWord = &quot;hit&quot;, endWord = &quot;cog&quot;, wordList = [&quot;hot&quot;,&quot;dot&quot;,&quot;dog&quot;,&quot;lot&quot;,&quot;log&quot;]
<strong>Output:</strong> []
<strong>Explanation:</strong> The endWord &quot;cog&quot; is not in wordList, therefore there is no valid transformation sequence.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= beginWord.length &lt;= 5</code></li>
	<li><code>endWord.length == beginWord.length</code></li>
	<li><code>1 &lt;= wordList.length &lt;= 500</code></li>
	<li><code>wordList[i].length == beginWord.length</code></li>
	<li><code>beginWord</code>, <code>endWord</code>, and <code>wordList[i]</code> consist of lowercase English letters.</li>
	<li><code>beginWord != endWord</code></li>
	<li>All the words in <code>wordList</code> are <strong>unique</strong>.</li>
	<li>The <strong>sum</strong> of all shortest transformation sequences does not exceed <code>10<sup>5</sup></code>.</li>
</ul>

class Solution {
private:
    queue<string> bfs_traversal;
    bool end_word_reached;
    
    vector<vector<string>> word_ladder;
    
    unordered_set<string> word_list;
            
    unordered_map<string, unordered_set<string>> parent_list;
    
    unordered_map<string, int> shortest_path_len;
    
    vector<string> single_ladder;
    
    unordered_map<string, vector<string>> adj_map;
    
    unordered_map<string, bool> processed_words;
    
    void fill_adj_map(string beginWord, vector<string>& wordList) {
        fill_one_dist_string(beginWord);
        for ( int i = 0; i < wordList.size(); i++ ) {
            fill_one_dist_string(wordList[i]);
        }
        
        /*for ( int i = 0; i < wordList.size(); i++ ) {
            cout<<wordList[i]<<" "<<adj_map[wordList[i]].size()<<endl;
        }*/
    }
    
    inline void fill_one_dist_string(string word) {
        string orig_word = word;
        for ( int i = 0; i < word.length(); i++ ) {
            char orig_char = word[i];
            for ( int j = 0; j < 26; j++ ) {
                if ( orig_char != ('a' + j) ) {
                    word[i] = ('a' + j);
                    if ( word_list.find(word) != word_list.end() ) {
                        adj_map[orig_word].push_back(word);
                    }
                }
            }
            word[i] = orig_char;
        }
    }
    
    void fill_word_list(vector<string>& wordList) {
        for ( int i = 0; i < wordList.size(); i++ ) {
            word_list.insert(wordList[i]);
            shortest_path_len[wordList[i]] = -1;
            processed_words[wordList[i]] = false;
        }
    }
    
    inline void process_word(string word, int curr_level, string endWord) {
        int next_level = curr_level + 1;
        for ( int i = 0; i < adj_map[word].size(); i++ ) {
            if ( shortest_path_len[adj_map[word][i]] == -1 || shortest_path_len[adj_map[word][i]] == next_level ) {
                shortest_path_len[adj_map[word][i]] = next_level;
                parent_list[adj_map[word][i]].insert(word);
                if ( adj_map[word][i] != endWord && !end_word_reached ) {
                    bfs_traversal.push(adj_map[word][i]);
                }
                else {
                    end_word_reached = true;
                }
            }
        }
    }
    
    void find_word_ladder(string beginWord, string endWord) {
        bfs_traversal.push(beginWord);
        end_word_reached = false;
        int curr_level = 0;
        
        while ( !bfs_traversal.empty() ) {
            int n = bfs_traversal.size();
            curr_level++;
            while ( n > 0 ) {
                n--;
                string curr_word = bfs_traversal.front();
                bfs_traversal.pop();
                if ( processed_words[curr_word] ) {
                    continue;
                }
                processed_words[curr_word] = true;
                //cout<<"before inserting: "<<curr_word<<" "<<bfs_traversal.size()<<endl;
                process_word(curr_word, curr_level, endWord);
                //cout<<"after inserting: "<<curr_word<<" "<<bfs_traversal.size()<<endl<<endl;
            }
            if (end_word_reached) {
                break;
            }
        }
    }
    
    void run_dfs_single_ladder(string& curr_word, string& begin_word) {
        single_ladder.push_back(curr_word);
        if ( curr_word == begin_word ) {
            word_ladder.push_back(single_ladder);
        }
        else {
            auto itr = parent_list[curr_word].begin();
            while ( itr != parent_list[curr_word].end() ) {
                string child = *itr;
                run_dfs_single_ladder(child, begin_word);
                itr++;
            }
        }
        single_ladder.pop_back();
    }
    
    void reverse_word_ladder() {
        for ( int i = 0; i < word_ladder.size(); i++ ) {
            for ( int j = 0; j < word_ladder[i].size() / 2; j++ ) {
                string temp = word_ladder[i][j];
                word_ladder[i][j] = word_ladder[i][word_ladder[i].size() - 1 - j];
                word_ladder[i][word_ladder[i].size() - 1 - j] = temp;
            }
        }
    }
    
    void print_parent_list() {
        auto itr = parent_list.begin();
        while ( itr != parent_list.end() ) {
            cout<<itr->first<<": ";
            auto itr1 = itr->second.begin();
            while ( itr1 != itr->second.end() ) {
                cout<<*itr1<<" ";
                itr1++;
            }
            itr++;
            cout<<endl;
        }
    }
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        fill_word_list(wordList);
        fill_adj_map(beginWord, wordList);
        find_word_ladder(beginWord, endWord);
        single_ladder.clear();
        if ( !end_word_reached ) {
            return word_ladder;
        }
        print_parent_list();
        run_dfs_single_ladder(endWord, beginWord);
        reverse_word_ladder();
        return word_ladder;
    }
};
18000