<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>

from collections import deque

class Solution:

    """
    APPROACH: BFS
    We'll perform an exploration where at each step we'll move towards word if it's distance is 1.
    At next step, we will not consider any word that was matched previously, as that's a loop.
    Once word = endWord, we'll return path length (+1)
    
    no w1 -> w2 caching: "25,218,462 checks" for case 5
    t: O((NL)^2), s:O(N^2)

    Optimization 1: Cache w1 -> w2 within wordlist. 7,782,859 checks
    
    Optimization 2: Instead of checking N words with N - 1, we'll simply add it's variations 
    in dict
    """
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        
        DELIMITER = '*'
        g, wordL = defaultdict(list), len(beginWord)

        def getWordTransformations(word: str) -> List[str]:
            trans = []
            for idx in range(len(word)):
                trans.append(word[:idx] + DELIMITER + word[idx+1:])
            return trans

        for word in wordList:
            for wordTrans in getWordTransformations(word):
                g[wordTrans].append(word)
        
        # print(g)

        # Now perform BFS
        q = [(beginWord, 1)]
        seenWords = set() # skip these to avoid looping

        while q:
            # print(q)
            newQ, removeWords = [], set()

            for word, path in q:
                if word == endWord:
                    return path

                for wordTrans in getWordTransformations(word):
                    for nextWord in g[wordTrans]:
                        if nextWord not in seenWords:
                            newQ.append((nextWord, path + 1))
                            removeWords.add(nextWord)
            
            q = newQ
            seenWords.update(removeWords)

        return 0

                        

        







24487