<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 defaultdict, deque
from itertools import product

class Solution:
    """
    Sounds like bfs.
    We can create a graph of the words in the dictionary + start word.
    Two nodes have an edge if their hamming distance is 1.
    Then perform bfs between source and target to measure distance.

    How to measure distance between each pair of words?
    Naive: O(m^2)

    Improvement:
    We do not need to construct the entire graph. only the subgraph that is at distance <= k.
    Furthermore, we could compute the existence of an edge lazily. 
    Time complexity: O(D(s, k)m^2) < O(n^2m^2)
    Space complexity: O(n)

    Algorithm:
    queue = (source, 0)
    visited = {source}
    while queue not empty:
        u, d = next(queue)
        if u == target:
            return d
        for v in V - visited:
            if has_edge(u, v):
                visited.add(v)
                queue.append((v, d + 1))
            
    """
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        word_set = set(wordList)
        queue = deque([(beginWord, 0)])
        visited = set(beginWord)
        while len(queue) > 0:
            u, d = queue.popleft()

            if u == endWord:
                return d + 1

            for v in word_set - visited:
                if has_edge(u, v):
                    visited.add(v)
                    queue.append((v, d + 1))

        return 0

def has_edge(word1: str, word2: str) -> bool:
    count = 0
    for c1, c2 in zip(word1, word2):
        if c1 != c2:
            count += 1
            if count > 1:
                return False
    return True
18237