<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>the <strong>number of words</strong> in the <strong>shortest transformation sequence</strong> from</em> <code>beginWord</code> <em>to</em> <code>endWord</code><em>, or </em><code>0</code><em> if no such sequence exists.</em></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> 5
<strong>Explanation:</strong> One shortest transformation sequence is &quot;hit&quot; -&gt; &quot;hot&quot; -&gt; &quot;dot&quot; -&gt; &quot;dog&quot; -&gt; cog&quot;, which is 5 words long.
</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> 0
<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;= 10</code></li>
	<li><code>endWord.length == beginWord.length</code></li>
	<li><code>1 &lt;= wordList.length &lt;= 5000</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>
</ul>

class Solution {

/**
- do a graph which s1->s2 iff s1 differs on at most one char from s2
- if beginword cannot be transformed to any string return 0, if endword not in wordlist return 0
- if so, get shortest path from beginWord to endword using bfs and each vertex has min distance, since 
 its bfs, the first one to get to the path, is the shortest one.

 O(n^2 + n^2logn + n^2) = O(n^2logn)
*/
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        // check for endWord in wordList

        bool endWordFound = false;
        for(auto w : wordList){
            if(w == endWord){
                endWordFound = true;
                break;
            }
        }

        if(!endWordFound)
            return 0;

        wordList.push_back(beginWord);
        wordList.push_back(endWord);


        unordered_map<string,vector<string>> g;

        // build the graph
        buildG(g,wordList,beginWord,endWord);

        for(auto p : g){
            cout << p.first << ":\n";
            for(auto q : p.second){
                cout << q << " ";
            }
            cout << "\n";
        }



        // check if you cant transform beginWord to a word within wordList
        if(g[beginWord].size() == 0 || g[beginWord].size() == 0)
            return 0;


        //bfs to check shortest path

        int shortest = 0;

        queue<pair<string,int>> q; // node, depth

        q.push({beginWord,0});

        unordered_map<string,int> vis;

        while(!q.empty()){
            auto p = q.front();
            string node = p.first;
            int depth = p.second;
            q.pop();

            vis[node] = 1;

            for(auto nei : g[node]){
                if(nei == endWord){
                    shortest = depth+1;
                    return shortest+1;
                }  

                if(vis[nei]){
                    continue;
                }


                q.push({nei,depth+1});
            }

        }

        

        return 0;


    }


    void buildG(unordered_map<string,vector<string>> &g, vector<string> &wordList ,string &beginWord, string &endWord){
        
        for(auto w1 : wordList){
            for(auto w2 : wordList){
                if(w1 == w2) continue;

                if(canConnect(w1,w2)){
                    g[w1].push_back(w2);
                }

            }
        }

    }


    bool canConnect(string &w1, string &w2){
        // since are sorted, we have to guarantee that they have connected

        int cntDistinct = 0;
        for(int i = 0; i < w1.size(); i++){
            if(w1[i] != w2[i]){
                cntDistinct++;
            }
        }

        return cntDistinct == 1;

    }
};
60325