Word Ladder

Word Ladder hides its graph completely. You get a start word, an end word and a word list — no edges anywhere. The first step is to see that each word is a node, that two words one letter apart share an edge, and that "shortest sequence" means BFS. The second step is to build those edges without comparing every word with every other.

The problem

You are given a start word, an end word and a list of allowed words, all of the same length. A ladder changes one letter at a time, and every word after the start must be in the list. Return the number of words in the shortest ladder from the start word to the end word, counting both ends. Return 0 if no ladder exists.

Example 1. Start cold, end warm, list [cord, card, ward, warm, word, worm, corm, wore, bold] → 5. One shortest ladder is cold → cord → word → ward → warm. (cold → cord → card → ward → warm is another, also 5 words.)

Example 2. Start cold, end heat, same list → 0. heat is not in the list.

Constraints. Up to 5,000 words in the list, each 1 to 10 lowercase letters.

Clarifying questions

• Must the start word be in the list? No. The end word must be, or the answer is 0.
• Count words or changes? Words, including both ends: 4 changes means 5 words.
• Are all words the same length? Yes.
• Can the list have duplicates? Assume it may; a visited set handles it.

Approach 1: the simple way

Build the graph explicitly. Compare every pair of words; if they differ in exactly one position, join them with an edge. Then run BFS from the start word.

1from collections import deque234def ladder_length_brute(begin: str, end: str, words: list[str]) -> int:5    """Compare every pair of words to build the graph, then BFS."""6    nodes = list(dict.fromkeys([begin] + words))7    if end not in words:8        return 0910    def one_apart(a: str, b: str) -> bool:11        return sum(x != y for x, y in zip(a, b)) == 11213    graph = {w: [] for w in nodes}14    for i, a in enumerate(nodes):15        for b in nodes[i + 1:]:16            if one_apart(a, b):17                graph[a].append(b)18                graph[b].append(a)19    steps = {begin: 1}20    queue = deque([begin])21    while queue:22        word = queue.popleft()23        if word == end:24            return steps[word]25        for nxt in graph[word]:26            if nxt not in steps:27                steps[nxt] = steps[word] + 128                queue.append(nxt)29    return 0

The BFS is fine. The graph-building is not. With N words of length L, there are N²/2 pairs and each comparison reads L letters: O(N² × L). With 5,000 words of 10 letters, that is 12.5 million pairs and 125 million letter comparisons — many seconds in Python, and most of the pairs, like cold and ward, were never going to be neighbours.

The key insight

Two words are neighbours exactly when they become the same string after one position is replaced by a wildcard. cold and cord both turn into co*d. cord and word both turn into *ord.

So group the words by these wildcard patterns. Each word of length L belongs to L patterns — *old, c*ld, co*d, col* for cold — and its neighbours are the other words in those same groups. Building the groups costs O(N × L²): N words, L patterns each, O(L) to build each pattern string. No pair of words is ever compared.

Then run BFS from the start word, generating neighbours through the patterns. The graph is implicit: it is never built as an adjacency list, only looked up when needed.

Approach 2: BFS over wildcard buckets

1from collections import defaultdict, deque234def ladder_length(begin: str, end: str, words: list[str]) -> int:5    """BFS where neighbours come from wildcard buckets like 'c*ld'."""6    if end not in words:7        return 08    buckets: dict[str, list[str]] = defaultdict(list)9    for w in words:10        for i in range(len(w)):11            buckets[w[:i] + "*" + w[i + 1:]].append(w)12    steps = {begin: 1}13    queue = deque([begin])14    while queue:15        word = queue.popleft()16        if word == end:17            return steps[word]18        for i in range(len(word)):19            key = word[:i] + "*" + word[i + 1:]20            for nxt in buckets.pop(key, []):     # each bucket is used once21                if nxt not in steps:22                    steps[nxt] = steps[word] + 123                    queue.append(nxt)24    return 0

Step by step:

1. If the end word is not in the list, stop: 0.
2. Put every word into its L wildcard buckets.
3. BFS from the start word. steps records each word's ladder length and doubles as the visited set.
4. For each popped word, look at its L patterns. Every word in those buckets is one letter away.
5. buckets.pop removes a bucket once it has been used. Any later word reaching the same bucket would find only words that are already visited, so emptying it saves repeated work.

Dry run on Example 1. The queue is shown after each word is expanded.

The answer is 5. BFS reached warm level by level, so no shorter ladder can exist.

Complexity. Building the buckets is O(N × L²). The BFS visits each word once; for each it builds L patterns at O(L) each, and every bucket entry is read once in total because buckets are removed after use. Total O(N × L²) time and space. With 5,000 words of 10 letters, that is about 500,000 character operations instead of 125 million.

Approach 3: bidirectional BFS

BFS from one end explores a ball of words that grows with every level. If each word has about b neighbours and the ladder has d steps, one-sided BFS touches about b^d words. Searching from both ends and stopping when the two frontiers meet touches about 2 × b^(d/2) — for b = 10 and d = 6, that is 2,000 words instead of 1,000,000. Always expand the smaller frontier. The answer is the same; the code is longer, so offer it as the improvement once the one-sided version works.

Edge cases

• End word not in the list → 0, before any search.
• Start word in the list → it is already in steps, so it is never re-added.
• Start and end one letter apart → 2.
• No ladder → the queue empties: 0.
• Words of length 1 → every word shares the single bucket *, and the ladder has 2 words.

Follow-ups

• "Return every shortest ladder, not just the length." BFS level by level while recording each word's parents on the previous level, then backtrack from the end word. This is the hard variant (Word Ladder II).
• "Changing some letters costs more than others." Edges now have weights, so BFS is no longer correct: use Dijkstra.
• "Generate neighbours by trying all 26 letters in each position." Also O(N × 26 × L²) and needs no buckets; it is better when the list is huge and words are short. Mention both.