<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
# class Solution:
#     def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
#         wordList = set(wordList)
#         if endWord not in wordList:
#             return 0

#         wordList.add(beginWord)

#         patternAdjList = self.makePatternAdjList(wordList)
#         return self.bfs(beginWord, endWord, patternAdjList)


#     def makePatternAdjList(self, wordList):
#         patternsToWordsDict = defaultdict(set)

#         for word in wordList:
#             for charIdx in range(len(word)):
#                 pattern = word[:charIdx] + '*' + word[charIdx + 1:]
#                 patternsToWordsDict[pattern].add(word)

#         return patternsToWordsDict

#     def bfs(self, beginWord, endWord, patternAdjList):
#         queue = deque([(beginWord, 1)])
#         visited = set()
#         visited.add(beginWord)

#         while queue:
#             # Pop node and level
#             word, level = queue.popleft()
#             # Process node
#             if word == endWord:
#                 return level
#             visited.add(word)
#             # Create all possible patterns for word, these will be neighbours
#             # to add to queue
#             for charIdx in range(len(word)):
#                 pattern = word[:charIdx] + '*' + word[charIdx + 1:]

#                 for neighbour in patternAdjList[pattern]:
#                     if neighbour not in visited:
#                         visited.add(neighbour)
#                         queue.append((neighbour, level + 1))

#         return 0

############### BIDIRECTIONAL BFS ###############
from collections import defaultdict, deque
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordList = set(wordList)
        wordList.add(beginWord)
        if endWord not in wordList:
            return 0

        patternsAdjList = self.makePatternAdjList(wordList)
        return self.bidirectional_bfs(beginWord, endWord, wordList, patternsAdjList)

    def makePatternAdjList(self, wordList):
        patternsDict = defaultdict(set)

        for word in wordList:
            for charIdx in range(len(wordList)):
                pattern = word[:charIdx] + '*' + word[charIdx + 1:]
                patternsDict[pattern].add(word)

        return patternsDict

    def bidirectional_bfs(self, beginWord, endWord, wordList, patternsAdjList):
        top_queue = deque([(beginWord, 1)])
        bottom_queue = deque([(endWord, 1)])

        # 2 visited dictionaries instead of sets, because we need to know level 
        # that each directional BFS encountered a node.
        # Then just return the 2 levels added together, since the meeting point
        # of 2 directional BFS is in the middle. 
        visited_top = {beginWord: 1}
        visited_bottom = {endWord: 1}

        while top_queue and bottom_queue:
            level = self.bfs(top_queue, visited_top, visited_bottom, patternsAdjList) or \
                self.bfs(bottom_queue, visited_bottom, visited_top, patternsAdjList)
            if level:
                return level
        return 0

    def bfs(self, queue, visited, other_visited, patternsAdjList):
        # Pop node off
        word, level = queue.popleft()
        # Process node
        for charIdx in range(len(word)):
            pattern = word[:charIdx] + '*' + word[charIdx + 1:]

            for neighbour in patternsAdjList[pattern]:
                # If node already visited by opposite direction BFS, 
                # then we have found meeting point of 2 BFS searches.
                # So return this BFS' level + other BFS' level
                if neighbour in other_visited:
                    return level + other_visited[neighbour]
                # Otherwise, add neighbours to queue
                if neighbour not in visited:
                    visited[neighbour] = level + 1
                    queue.append((neighbour, level + 1))
        return None

23362