Word Ladder — Shortest Transformation Path with BFS and a Wildcard Trick

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.

Constraints:

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• All words consist of lowercase English letters.

Input:  beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog".

Input:  beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: endWord "cog" is not in wordList, so no sequence ends in cog.

Input:  beginWord = "a", endWord = "c", wordList = ["a","b","c"]
Output: 2

Why This Problem Matters#

LeetCode 127 Word Ladder is a fan favorite at Amazon, Google, Meta, and Microsoft because it tests three things in one shot:

1. Modeling: turning a string puzzle into an implicit graph where each word is a node and adjacency means "differs by one letter."
2. Shortest path: recognizing that BFS — not DFS — is the right tool when the graph is unweighted.
3. Optimization: using a wildcard pattern map (h*t, *ot, ho*) to reduce neighbor lookups from O(N * L) per word to O(L), where N is the dictionary size and L is the word length.

This same toolkit unlocks Word Ladder II (return all shortest sequences), Open the Lock (LC 752), Minimum Genetic Mutation (LC 433), and many "shortest steps" interview questions.

The Core Insight#

Brute force makes the graph explicit: for each pair of words, check if they differ by one letter. That is O(N^2 * L) and times out for N = 5000.

The trick is to never enumerate all neighbors of a word. Instead, for each word in the dictionary, precompute its L wildcard patterns. For example, "hot" produces "*ot", "h*t", "ho*". Two words are neighbors if and only if they share at least one wildcard pattern.

Now BFS works like this:

1. Build a map from pattern to list of matching words.
2. Push beginWord into a queue at level 1.
3. Pop a word, generate its L patterns, look up the candidate words for each pattern, push the new ones.
4. When endWord is popped, return its level.

Each word is visited at most once. Each word generates L patterns. Each pattern points to a list of candidates whose total length across the entire BFS is bounded by O(N * L). Total time is O(N * L^2).

A further ~2x speedup is bidirectional BFS: search from beginWord and endWord simultaneously, always expanding the smaller frontier. The frontiers meet in the middle, halving the explored breadth.

Visual Dry Run#

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

Pattern map (excerpt):

BFS:

Length = 5 (number of words: hit, hot, dot, dog, cog). Return 5.

Solution (Optimal)#

# Python — BFS with wildcard pattern map, O(N * L^2) time, O(N * L^2) space
from collections import deque, defaultdict
 
def ladderLength(beginWord: str, endWord: str, wordList: list[str]) -> int:
    if endWord not in wordList:
        return 0
 
    L = len(beginWord)
    pattern_map = defaultdict(list)
    for word in wordList:
        for i in range(L):
            pattern_map[word[:i] + '*' + word[i+1:]].append(word)
 
    queue = deque([(beginWord, 1)])
    visited = {beginWord}
 
    while queue:
        word, level = queue.popleft()
        for i in range(L):
            pattern = word[:i] + '*' + word[i+1:]
            for neighbor in pattern_map[pattern]:
                if neighbor == endWord:
                    return level + 1
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, level + 1))
            pattern_map[pattern] = []  # avoid revisiting through same pattern
 
    return 0

// JavaScript — BFS with wildcard pattern map
function ladderLength(beginWord, endWord, wordList) {
    const wordSet = new Set(wordList);
    if (!wordSet.has(endWord)) return 0;
 
    const L = beginWord.length;
    const patternMap = new Map();
    for (const word of wordList) {
        for (let i = 0; i < L; i++) {
            const pat = word.slice(0, i) + '*' + word.slice(i + 1);
            if (!patternMap.has(pat)) patternMap.set(pat, []);
            patternMap.get(pat).push(word);
        }
    }
 
    const queue = [[beginWord, 1]];
    const visited = new Set([beginWord]);
 
    while (queue.length) {
        const [word, level] = queue.shift();
        for (let i = 0; i < L; i++) {
            const pat = word.slice(0, i) + '*' + word.slice(i + 1);
            for (const next of (patternMap.get(pat) || [])) {
                if (next === endWord) return level + 1;
                if (!visited.has(next)) {
                    visited.add(next);
                    queue.push([next, level + 1]);
                }
            }
            patternMap.set(pat, []);
        }
    }
 
    return 0;
}

Complexity:

Common Mistakes#

1. Forgetting the endWord in wordList early-out. If the end word is not in the dictionary, no transformation can end there. Returning 0 immediately saves work.

2. Counting nodes vs edges. The answer is the number of words in the path, not the number of transformations. "hit" to "cog" is 4 transformations but length 5.

3. Generating neighbors by mutating each letter into 26 alternatives. That is O(N * L * 26) per BFS step and slower than the pattern map for large N.

4. Not marking visited. A word can be reached by many neighbors. Without a visited set you revisit it endlessly and explode time complexity.

5. Using list.pop(0) in Python. That is O(N). Use collections.deque.popleft(), which is O(1).

Interview Tips#

• Start by pointing out that this is "shortest path on an implicit graph, so BFS." That single sentence frames the entire solution.
• Justify the wildcard map: "Without it, finding neighbors is O(N * L) per word, which is too slow."
• If the interviewer asks for further speedup, mention bidirectional BFS. Be ready to describe the alternation rule: always expand the smaller frontier.
• Mention LC 126 Word Ladder II as the natural follow-up — same BFS but record parents and reconstruct all shortest paths.

Follow-up Questions#

1. Word Ladder II (LC 126). Return all shortest transformation sequences. Use BFS to compute level distances, then DFS or backtracking to reconstruct paths.
2. Open the Lock (LC 752). BFS with 0000-style states and dead ends blocked.
3. Minimum Genetic Mutation (LC 433). Same algorithm with a 4-letter alphabet ACGT.
4. What if the dictionary is huge (millions of words)? Bidirectional BFS or A* with edit-distance heuristic.
5. What if changes can also include insertions and deletions? The graph is no longer a Hamming-distance neighborhood — different problem.

Key Takeaways#

• Word Ladder is BFS on an implicit unweighted graph; BFS is required because we need the shortest sequence.
• Build a wildcard pattern map (h*t, *ot, ...) so each word's neighbors can be found in O(L) rather than O(N * L).
• Track visited words to avoid revisiting; clear visited patterns after they are processed for an extra constant-factor speedup.
• Time complexity is O(N * L^2); bidirectional BFS roughly halves the explored breadth.
• The same template solves Open the Lock, Minimum Genetic Mutation, and any "shortest steps from A to B in an implicit transformation graph" problem.
• Word Ladder II (LC 126) extends the technique by recording parents during BFS and reconstructing all shortest paths.