Word Ladder (LeetCode 127): BFS with Wildcard Patterns in Python

Word Ladder (LeetCode 127) asks for the length of the shortest chain from one word to another, changing one letter at a time, where every step must be in a given list. Shortest path with equal steps means breadth-first search. The trick that makes it fast is grouping words by wildcard patterns such as h*t, so you don't compare every pair of words.

The problem

Given beginWord, endWord, and a list of words, return the number of words in the shortest transformation sequence from beginWord to endWord, counting both ends. Each step changes exactly one letter, and each word you move to must be in the list. Return 0 if there's no such sequence.

Why breadth-first search

Treat each word as a node, with an edge between two words that differ by one letter. Every edge costs one step, so the shortest sequence is the shortest path in an unweighted graph, and breadth-first search finds it the first time it reaches the end word.

Brute force edge building

Comparing every pair of words to see whether they differ by one letter costs O(N squared times L) for N words of length L. With thousands of words that's slow. Better: generate neighbors from patterns.

Approach: wildcard patterns

Replace each letter in turn with *. hot becomes *ot, h*t, and ho*. Two words are neighbors exactly when they share a pattern. Build a map from pattern to the words that fit it, then run the search using it.

from collections import deque, defaultdict

def ladder_length(begin_word, end_word, word_list):
    words = set(word_list)
    if end_word not in words:
        return 0
    patterns = defaultdict(list)
    for w in words | {begin_word}:
        for i in range(len(w)):
            patterns[w[:i] + "*" + w[i + 1:]].append(w)
    queue = deque([(begin_word, 1)])
    seen = {begin_word}
    while queue:
        word, steps = queue.popleft()
        if word == end_word:
            return steps
        for i in range(len(word)):
            key = word[:i] + "*" + word[i + 1:]
            for nxt in patterns[key]:
                if nxt not in seen:
                    seen.add(nxt)
                    queue.append((nxt, steps + 1))
            patterns[key] = []
    return 0

Two details matter. The begin word is added to the pattern map even if it isn't in the list, since you start from it. And after a pattern's words are visited, patterns[key] = [] empties it so the same group isn't scanned again from every other word that shares the pattern. That keeps the total work linear in the number of patterns.

Complexity

Building patterns takes O(N times L), and each pattern string costs O(L) to build, so about O(N times L squared) in total. The search touches each word once and each pattern group once, for the same bound. Space is O(N times L squared) for the pattern map, since every word is stored under L keys of length L.

Going faster: bidirectional search

Run one search from the begin word and one from the end word, and always expand the smaller frontier. They meet in the middle, so each side only searches half the depth. It's worth mentioning if the interviewer asks how to speed it up, and it's more code than most interviews expect you to write.

Common mistakes

• Returning the number of changes instead of the number of words. The sequence includes beginWord, so the example gives 5, not 4.
• Not checking that endWord is in the list before searching.
• Building neighbors with a pairwise comparison and timing out.
• Letting the search revisit words, which loops or slows it.
• Using DFS, which finds a path but not the shortest one.

Edge cases to test

How to explain it in an interview

1. Reframe it as a graph and say why breadth-first search finds the shortest path.
2. Say the pairwise comparison is too slow, and introduce wildcard patterns.
3. Write the pattern map, the queue, and the visited set.
4. Say that you count words, not edits, and show the first example.
5. Give the complexity and mention bidirectional search.

I tested the code above against a plain pairwise breadth-first search on 20,000 random small word lists, plus the two examples in the table, before publishing. A quick random check like that is a good habit when you practice.

Related practice

See our Big O cheat sheet for the complexity terms, the LeetCode Blind 75 list for what to practice next, and the coding interview assistant guide for how to practice.

Talk through your approach aloud while you code. A transcript shows whether you stated the key observation before writing. Follow the employer's rules on AI tools in any live assessment.