Word Ladder — BFS Shortest Transformation

Problem

Given beginWord, endWord, and wordList, find the length of shortest transformation sequence (each step differs by 1 letter, each word in list).

Approach — BFS with Wildcard Pattern Grouping

Preprocess words into pattern groups (h*t → hot, hat). BFS from beginWord using pattern-to-words map for O(1) neighbour lookup.

Time: O(M² * N) where M=word length, N=dict size | Space: O(M² * N)

Solutions

Python — BFS Wildcard Patterns

from collections import deque, defaultdict
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
        if endWord not in wordList: return 0
        L=len(beginWord)
        adj=defaultdict(list)
        for word in wordList:
            for i in range(L):
                adj[word[:i]+'*'+word[i+1:]].append(word)
        visited={beginWord}; q=deque([(beginWord,1)])
        while q:
            word,level=q.popleft()
            for i in range(L):
                pattern=word[:i]+'*'+word[i+1:]
                for nb in adj[pattern]:
                    if nb==endWord: return level+1
                    if nb not in visited: visited.add(nb); q.append((nb,level+1))
        return 0

Python — BFS Direct

from collections import deque
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
        words=set(wordList)
        if endWord not in words: return 0
        q=deque([(beginWord,1)])
        visited={beginWord}
        while q:
            word,steps=q.popleft()
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    nw=word[:i]+c+word[i+1:]
                    if nw==endWord: return steps+1
                    if nw in words and nw not in visited:
                        visited.add(nw); q.append((nw,steps+1))
        return 0

Complexity

Time: O(M² * N) | Space: O(M² * N)