Problem 44 · Graphs

Word Ladder

HardClassic DSA & systems

01Problem

Given beginWord, endWord and a word list, return the number of words in the shortest transformation sequence changing one letter at a time, with every intermediate word in the list; return 0 if impossible.

02Key insight

Unweighted shortest path means BFS. Bucket words by wildcard patterns (h*t) so neighbor generation is O(L) lookups instead of comparing against every word; bidirectional BFS further shrinks the frontier.

03Solution

solution.pypython23 lines

from collections import defaultdict, deque

def ladder_length(begin: str, end: str, words: list[str]) -> int:
    word_set = set(words)
    if end not in word_set:
        return 0
    buckets: dict[str, list[str]] = defaultdict(list)
    for w in word_set | {begin}:
        for i in range(len(w)):
            buckets[w[:i] + "*" + w[i + 1:]].append(w)
    seen = {begin}
    queue = deque([(begin, 1)])
    while queue:
        word, dist = queue.popleft()
        if word == end:
            return dist
        for i in range(len(word)):
            key = word[:i] + "*" + word[i + 1:]
            for nxt in buckets.pop(key, []):  # pop: each bucket is expanded once
                if nxt not in seen:
                    seen.add(nxt)
                    queue.append((nxt, dist + 1))
    return 0

Try it first.

TimeO(N*L^2)

SpaceO(N*L^2)

tests.py · 3 passing

tests.pypython3 lines

assert ladder_length("hit", "cog", ["hot","dot","dog","lot","log","cog"]) == 5
assert ladder_length("hit", "cog", ["hot","dot","dog","lot","log"]) == 0
assert ladder_length("a", "c", ["a","b","c"]) == 2

04Staff-level follow-up

Dictionary of 100M words? Precompute the wildcard index offline in a KV store and run bidirectional BFS, which explores ~2*b^(d/2) nodes instead of b^d.