Word Ladder — BFS on an Implicit Graph of Word Transformations

Problem Statement#

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence beginWord → s1 → s2 → ... → sk such that every adjacent pair of words differs by exactly one letter, every si for 1 <= i <= k is in wordList, and sk == endWord. Given beginWord, endWord, and wordList, return the number of words in the shortest transformation sequence, or 0 if no such sequence exists.

Constraints:

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord, endWord, and wordList[i] consist of lowercase English letters.
• beginWord != endWord
• All words in wordList are unique.

Example 1:

Input:  beginWord = "hit", endWord = "cog",
        wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: hit → hot → dot → dog → cog (5 words in sequence)

Example 2:

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

Example 3:

Input:  beginWord = "a", endWord = "c", wordList = ["a","b","c"]
Output: 2
Explanation: a → c (direct one-letter change, 2 words in the sequence)

Why This Problem Matters#

Word Ladder is one of the most famous graph problems in the FAANG interview canon — Amazon and Google ask it regularly. It tests whether you can recognise an implicit graph: the problem never gives you a node list or edge list. You have to construct the graph conceptually by realising each word is a node and two words are connected if they differ by exactly one letter.

The deeper lesson is BFS for minimum steps. Any time a problem asks for the shortest sequence of transformations with discrete steps, BFS is the answer. Word Ladder just happens to use string similarity as the edge condition instead of a grid adjacency, which trips up candidates who memorise "BFS = grid problems."

The wildcard pattern optimisation is also worth learning: instead of comparing every pair of words (O(N² * M)), you pregroup words by their patterns — replace each letter one at a time with *. Words sharing a pattern are immediate neighbours. This reduces neighbour lookup from O(N * M) to O(1) amortised, making the overall algorithm O(M² * N).

The Core Insight#

Model the problem as an unweighted graph where each word is a node and two words share an edge if they differ by exactly one letter. The shortest path from beginWord to endWord in this graph is the answer.

BFS on an unweighted graph always finds the shortest path because it explores all nodes at distance d before exploring any at distance d+1. The sequence length (number of words) equals the BFS depth plus one (we count words, not edges).

The expensive part is finding neighbours: naively, for each word you compare against all other words — O(N * M) per word, O(N² * M) total. The wildcard optimisation solves this: preprocess all dictionary words into a map from pattern to word list. The pattern for "hot" at position 1 is "h*t". Every word with the same pattern at that position is a one-letter neighbour. Lookup during BFS becomes O(M * average_pattern_group_size).

Visual Dry Run#

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

Build wildcard pattern map:

"*it" → ["hit"]
"h*t" → ["hit", "hot"]
"hi*" → ["hit"]
"*ot" → ["hot", "dot", "lot"]
"d*t" → ["dot"]
"do*" → ["dot", "dog"]
"*og" → ["dog", "log", "cog"]
"d*g" → ["dog"]
"l*t" → ["lot"]
"lo*" → ["lot", "log"]
"l*g" → ["log"]
"c*g" → ["cog"]
"co*" → ["cog"]

BFS trace:

cog == endWord → return 5.

Common Mistakes#

1. Not checking if endWord is in wordList. The problem states that sk == endWord must be in wordList. If endWord is not in the list, no valid sequence exists. Return 0 immediately. Forgetting this causes BFS to run indefinitely (or until the queue empties) without ever finding endWord.

2. Including beginWord in the visited set incorrectly. beginWord may or may not be in wordList. It does not need to be in the word list — the sequence starts with it regardless. Add beginWord to visited at the start to prevent re-visiting it, but do not require it to be in the word list.

3. Returning level instead of level + 1. The problem asks for the number of words in the sequence, not the number of edges. If beginWord starts at level 1 (not 0), endWord found at BFS depth d has sequence length d. Make sure you initialise the level counter correctly and return it including beginWord.

4. Mutating the word list during BFS without using a separate visited set. Some candidates delete words from the set as they visit them to avoid revisiting — this works but can cause issues if the set is iterated concurrently. Using a separate visited set is cleaner and avoids subtle bugs.

5. Naive O(N^2 * M) neighbour-finding without the pattern optimisation. For N=5000 and M=10, this is 500 million character comparisons — TLE. Either use the wildcard pattern map (preprocess once in O(M² * N), then O(M) lookup per word) or generate all 26 * M candidate words per BFS step and check membership in the word set (O(26 * M) per word, O(26 * M * N) total — still fast enough at these constraints).

6. Not marking a word as visited when enqueuing (only when dequeuing). If you mark words as visited only when you dequeue them, the same word can be enqueued multiple times. This does not affect correctness (you will still process it correctly the first time), but it multiplies queue size and blows up time complexity. Always mark visited when enqueuing.

Solutions#

Python#

from collections import deque, defaultdict
 
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
        # If endWord is not reachable, return immediately
        if endWord not in wordList:
            return 0
 
        L = len(beginWord)
 
        # Build wildcard pattern map: "h*t" → ["hot", "hat", ...]
        # Each word generates L patterns, one per letter position
        pattern_to_words = defaultdict(list)
        for word in wordList:
            for i in range(L):
                pattern = word[:i] + '*' + word[i + 1:]  # replace position i with *
                pattern_to_words[pattern].append(word)
 
        # BFS: (current_word, sequence_length_so_far)
        visited = {beginWord}
        queue = deque([(beginWord, 1)])  # beginWord counts as word #1 in the sequence
 
        while queue:
            word, level = queue.popleft()
 
            # Generate all L wildcard patterns for current word
            for i in range(L):
                pattern = word[:i] + '*' + word[i + 1:]
 
                # Check all words sharing this pattern (differ by exactly 1 letter at position i)
                for neighbor in pattern_to_words[pattern]:
                    if neighbor == endWord:
                        return level + 1  # found endWord; add 1 for endWord itself
 
                    if neighbor not in visited:
                        visited.add(neighbor)          # mark before enqueue to avoid duplicates
                        queue.append((neighbor, level + 1))
 
        return 0  # endWord not reachable

JavaScript#

var ladderLength = function(beginWord, endWord, wordList) {
    // If endWord is not in wordList, no transformation sequence can end there
    const wordSet = new Set(wordList);
    if (!wordSet.has(endWord)) return 0;
 
    const L = beginWord.length;
 
    // Build wildcard pattern map: "h*t" → ["hot", "hat", ...]
    const patternMap = new Map();
    for (const word of wordList) {
        for (let i = 0; i < L; i++) {
            // Replace character at position i with '*' to form a pattern
            const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
            if (!patternMap.has(pattern)) patternMap.set(pattern, []);
            patternMap.get(pattern).push(word);
        }
    }
 
    // BFS from beginWord; track [word, sequence_length]
    const visited = new Set([beginWord]);
    const queue = [[beginWord, 1]]; // beginWord is word #1 in the sequence
    let head = 0; // use index as queue pointer (avoids shift() O(n) cost)
 
    while (head < queue.length) {
        const [word, level] = queue[head++];
 
        // Try all L wildcard patterns for the current word
        for (let i = 0; i < L; i++) {
            const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
            const neighbors = patternMap.get(pattern) || [];
 
            for (const neighbor of neighbors) {
                if (neighbor === endWord) return level + 1; // found endWord
 
                if (!visited.has(neighbor)) {
                    visited.add(neighbor);              // mark visited at enqueue time
                    queue.push([neighbor, level + 1]);
                }
            }
        }
    }
 
    return 0; // endWord not reachable from beginWord
};

Complexity Analysis#

The wildcard pattern map and the 26-character generation approaches have similar practical performance. The pattern map has better worst-case when the alphabet is large; the 26-character generation is simpler to implement and sufficient for lowercase English.

Follow-up Questions#

Q: What if you need all shortest transformation sequences, not just the length? (LC 126) Use BFS to build a parents map (each word stores all predecessors that can reach it on a shortest path), then DFS backwards from endWord to beginWord to reconstruct all paths.

Q: What if words can have different lengths? Words of different lengths can never be one-letter transformations of each other (assuming "change one letter" means same position, same length). You would need to define what a valid transformation means for variable-length words, e.g., allowing one insertion or deletion.

Q: How would bidirectional BFS improve this? Bidirectional BFS runs BFS simultaneously from both beginWord and endWord, meeting in the middle. This reduces the search from O(b^d) to O(b^(d/2)) where b is branching factor and d is path length — a significant speedup for deep graphs.

Q: What if the dictionary is very large and we have many queries? Precompute the word graph once (adjacency list using pattern matching). For each query, run BFS from the given beginWord. Amortise the graph-building cost across all queries.

This Pattern Solves#

• LC 127 — Word Ladder (this problem)
• LC 126 — Word Ladder II (all shortest paths)
• LC 433 — Minimum Genetic Mutation (same pattern, genes instead of words)
• LC 1345 — Jump Game IV (BFS with value-to-index map instead of pattern map)
• LC 1091 — Shortest Path in Binary Matrix (grid BFS, same shortest-path idea)

Key Takeaways#

• Word Ladder models words as nodes and one-letter differences as edges in an implicit graph — BFS gives minimum transformations
• Build a pattern map: for each word, generate all wildcard patterns (replace each character with *) and group words by pattern
• Pattern map enables O(M) neighbor lookup per word instead of O(N*M) pairwise comparison — the key optimization
• Add words to the visited set before enqueueing to prevent reprocessing
• BFS level = transformation steps; return the level count when the target word is dequeued
• Time O(M^2 * N) with pattern map (M = word length, N = word list size); Space O(M^2 * N)
• This implicit graph + BFS pattern applies to any problem where neighbors are defined by a transformation rule (gene mutations, key combinations)