Problem Statement

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

  • Every adjacent pair of words differs by a single letter.
  • Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
  • sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Example 1:

Input: beginWord = "hit", 
endWord = "cog", 
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5
Explanation: One shortest transformation sequence is 
"hit" -> "hot" -> "dot" -> "dog" -> "cog", 
which is 5 words long.

Example 2:

Input: beginWord = "hit", 
endWord = "cog", 
wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, 
therefore there is no valid transformation sequence.

BFS: Iterative

from collections import defaultdict, deque
from typing import List, Dict

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
      
      # S: O(N*M)
      adj = self.m_adj(wordList)
      """
        beginWord = "hit", 
        endWord = "cog", 
        wordList = ["hot","dot","dog","lot","log","cog"]

        adj = \
        defaultdict(<class 'set'>,
            {'*og': {'dog', 'cog', 'log'},
             '*ot': {'lot', 'hot', 'dot'},
             'c*g': {'cog'},
             'co*': {'cog'},
             'd*g': {'dog'},
             'd*t': {'dot'},
             'do*': {'dog', 'dot'},
             'h*t': {'hot'},
             'ho*': {'hot'},
             'l*g': {'log'},
             'l*t': {'lot'},
             'lo*': {'lot', 'log'}})
      """
      seen = set()
      queue = deque([beginWord])
      dist = 0
      
      # T: O(N*M^2)
      # BFS Traversal
      while queue:
        dist += 1
        for _ in range(len(queue)):
          u = queue.popleft()

          if u == endWord:
            return dist

          # T: O(M^2)
          # We insert a step in the middle of the standard
          # "traverse each parent's neighbors" approach.
          # This intermediate step generates patterns
          # for each word in the adjacency list (set) and
          # then uses that pattern to get the neighbouring
          # words that are one letter modification away.
          for pat in self.m_patterns(u):
            for v in adj[pat]:
              if v not in seen:
                seen.add(v)
                queue.append(v)

      return 0

    # T: O(N*M^2)
    # S: O(N*M)
    def m_adj(self, words: List[str]) -> Dict[str, set]:
      """
          Loop through all of the words in the words list and
          create an adjacency list (set). The key will be the
          pattern and the values will be the words.
          In this problem, we can move from one word to another
          if the next word can be created by changing one letter.
          Example. word: "hit" -> keys = ["*it", "h*t", "hi*"].
          Any word that matches the previous three patterns is
          a valid next step.
      """
        adj = defaultdict(set)
        # T: O(M)
        for word in words:
          # T: O(M)
          patterns = set(self.m_patterns(word))
          for pat in patterns:
            adj[pat].add(word)

        return adj

    # T: O(M)
    def m_patterns(self, word: str) -> List[str]:
      n = len(word)
      return [word[:i] + "*" + word[i+1:] for i in range(n)]

Leetcode 127 Word Ladder