<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 itertools import zip_longest
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        bag = {}
        wordList = set(wordList)
        if endWord not in wordList:
            return 0
        Node.add(bag, beginWord)        
        for n in wordList:
            Node.add(bag, n)
        # print(bag)        
        return bag[beginWord].bfs(endWord) + 1

class Node:
    def __init__(self, word):
        self.name = word
        self.neig = []
    
    # def __repr__(self):
    #     return '<' + self.name + ' ' + str([n.name for n in self.neig]) + '>'
    
    def bfs(self, goal):
        seen = set([self.name])
        stack = [(self, 0)]
        i = 0
        while i < len(stack):
            cur, curPathLen = stack[i]
            if cur.name == goal:
                return curPathLen
            for n in cur.neig:
                if n.name in seen:
                    continue
                if n.name == goal:
                    return curPathLen + 1
                seen.add(n.name)
                stack.append((n, curPathLen + 1))
            i += 1
        return -1
    
    # def dfs(self, goal, cur=None):
    #     if cur is None:
    #         cur = [self.name]
    #     else:
    #         cur = cur + [self.name]
    #     if self.name == goal:
    #         return cur
    #     bestret = None
    #     for n in self.neig:
    #         if n.name in cur:
    #             continue
    #         ret = n.dfs(goal, cur)
    #         if ret is not None:
    #             if bestret is None or len(ret) < len(bestret):
    #                 bestret = ret
    #     return bestret

    @staticmethod
    def closeTo(n1, n2):
        d = 0
        for ci in range(len(n1.name)):
            if n1.name[ci] != n2.name[ci]:
                d += 1
            if d > 1:
                return False
        return True
    
    @staticmethod
    def add(bag, newword):
        if newword in bag:
            return
        n = Node(newword)
        bag[newword] = n
        for m in bag.values():
            if Node.closeTo(n, m):
                n.neig.append(m)
                m.neig.append(n)
21612