Word Ladder BFS Approach — Shortest Transformation Sequence

Word Ladder (LeetCode 127) is one of the most classic BFS problems. Given a start word, an end word, and a dictionary, find the length of the shortest transformation sequence where each step changes exactly one letter.

The Problem

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

Transformation: "hit" → "hot" → "dot" → "dog" → "cog"

Rules:

• Each transformation changes exactly one letter
• Every intermediate word must exist in wordList
• Return the number of words in the shortest sequence (including start and end)

Modeling as a Graph

Each word is a node. Two words are connected by an edge if they differ by exactly one letter. The problem becomes: find the shortest path from beginWord to endWord in this implicit graph.

Naive BFS: O(n x L) Neighbor Check

For each word, we could compare it against all other words in the list — but that is O(n^2 x L) total.

def are_neighbors(w1, w2):
    """Check if two words differ by exactly one letter. O(L)"""
    diff = 0
    for c1, c2 in zip(w1, w2):
        if c1 != c2:
            diff += 1
        if diff > 1:
            return False
    return diff == 1

Optimized BFS: Wildcard Pattern Matching

Instead of comparing every pair, we preprocess a map: for each word, generate its wildcard patterns by replacing one letter at a time with *.

"hot" → ["*ot", "h*t", "ho*"]
"dot" → ["*ot", "d*t", "do*"]

Words sharing a pattern (like "*ot") are neighbors. This lets us find neighbors in O(L) per word instead of O(n).

from collections import deque, defaultdict

def ladderLength(beginWord, endWord, wordList):
    """
    BFS with wildcard pattern optimization.
    Time: O(n * L^2) where n = word count, L = word length
    Space: O(n * L)
    """
    word_set = set(wordList)
    if endWord not in word_set:
        return 0

    # Build pattern → words map
    L = len(beginWord)
    pattern_map = defaultdict(list)

    for word in word_set:
        for i in range(L):
            pattern = word[:i] + "*" + word[i+1:]
            pattern_map[pattern].append(word)

    # BFS
    queue = deque([(beginWord, 1)])
    visited = {beginWord}

    while queue:
        word, length = queue.popleft()

        for i in range(L):
            pattern = word[:i] + "*" + word[i+1:]

            for neighbor in pattern_map[pattern]:
                if neighbor == endWord:
                    return length + 1

                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, length + 1))

            # Clear to avoid revisiting (optional optimization)
            pattern_map[pattern] = []

    return 0

Step-by-Step Trace

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

Pattern map (partial):
  "*ot" → ["hot", "dot", "lot"]
  "h*t" → ["hot"]
  "ho*" → ["hot"]
  "d*t" → ["dot"]
  "do*" → ["dot", "dog"]
  ...

BFS:
  Level 1: "hit" (length=1)
    Patterns: "*it", "h*t", "hi*"
    "*it" → no matches
    "h*t" → "hot" → enqueue ("hot", 2)
    "hi*" → no matches

  Level 2: "hot" (length=2)
    "*ot" → "dot", "lot" → enqueue both (length=3)
    "ho*" → no new matches

  Level 3: "dot" (length=3), "lot" (length=3)
    "do*" → "dog" → enqueue ("dog", 4)
    "lo*" → "log" → enqueue ("log", 4)

  Level 4: "dog" (length=4)
    "*og" → "dog", "log", "cog"
    "cog" == endWord → return 4 + 1 = 5

Alternative: Letter Substitution Without Preprocessing

If you prefer not building the pattern map upfront:

def ladderLength_substitute(beginWord, endWord, wordList):
    """Try all 26 substitutions per position. O(n * L * 26)."""
    word_set = set(wordList)
    if endWord not in word_set:
        return 0

    queue = deque([(beginWord, 1)])
    visited = {beginWord}

    while queue:
        word, length = queue.popleft()

        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                new_word = word[:i] + c + word[i+1:]

                if new_word == endWord:
                    return length + 1

                if new_word in word_set and new_word not in visited:
                    visited.add(new_word)
                    queue.append((new_word, length + 1))

    return 0

This approach is simpler and works well when L is small.

Bidirectional BFS

For large word lists, bidirectional BFS expands from both beginWord and endWord, meeting in the middle:

def ladderLength_bidir(beginWord, endWord, wordList):
    """Bidirectional BFS — much faster for large word lists."""
    word_set = set(wordList)
    if endWord not in word_set:
        return 0

    front = {beginWord}
    back = {endWord}
    visited = {beginWord, endWord}
    length = 1

    while front and back:
        # Expand the smaller frontier
        if len(front) > len(back):
            front, back = back, front

        next_front = set()
        for word in front:
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    new_word = word[:i] + c + word[i+1:]

                    if new_word in back:
                        return length + 1

                    if new_word in word_set and new_word not in visited:
                        visited.add(new_word)
                        next_front.add(new_word)

        front = next_front
        length += 1

    return 0

Complexity Analysis

Approach	Time	Space
Naive BFS	O(n^2 x L)	O(n)
Pattern map BFS	O(n x L^2)	O(n x L)
Letter substitution	O(n x L x 26)	O(n)
Bidirectional BFS	O(n x L x 26 / 2) avg	O(n)

Where n = number of words, L = word length.

Edge Cases

# End word not in word list
assert ladderLength("hit", "cog", ["hot","dot","dog"]) == 0

# Begin word equals end word
# (LeetCode guarantees they differ, but good to handle)

# No valid transformation path
assert ladderLength("hit", "cog", ["hot","dot","dog","lot","log"]) == 0

# Direct neighbor
assert ladderLength("hot", "dot", ["dot"]) == 2

When to Use This Pattern

Use BFS on word/string transformation when:

• Each step is a single character change
• You need the shortest sequence of transformations
• The valid words form a dictionary / set to check membership
• The state space (word length and dictionary size) is manageable

Related Problems

Problem	Key Difference
Word Ladder II (LC 126)	Find all shortest paths (harder)
Open the Lock (LC 752)	Digits instead of letters, deadends
Minimum Genetic Mutation (LC 433)	4-character alphabet (ACGT)
Edit Distance (LC 72)	DP, allows insert/delete/replace

Key Takeaways

• Word Ladder is a shortest-path problem on an implicit graph
• The wildcard pattern map turns O(n) neighbor lookup into O(L)
• Bidirectional BFS can halve the search space in practice
• Always check if endWord is in the word list before starting BFS
• This pattern applies to any “minimum steps to transform X into Y” problem