Word Ladder

Difficulty: Hard

Problem

Start at beginWord and reach endWord by changing exactly ONE letter per step, where every word you step onto must appear in wordList. Return the number of words in the SHORTEST such chain, counting both beginWord and endWord, or 0 if no chain exists. The tricky part is that the graph of connections between words is invisible until you build it.

Example

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: hit → hot → dot → dog → cog is a shortest ladder: 5 words. (hit → hot → lot → log → cog also works.)

Brute-force approach

No brute-force phase: recognizing the hidden graph and applying BFS IS the lesson.

Optimal approach

Key insight: The word 'shortest' hands you the algorithm. The only real work is seeing words as nodes, then it's the same BFS you've run five times, with neighbors generated on the fly.

BFS over the implicit word graph: each dequeued word spawns its one-letter variants; dictionary hits are discovered neighbors. First arrival at endWord is the shortest ladder.

Steps

  1. If endWord isn't in the word set, return 0
  2. Queue holds (word, ladderLength), starting with (beginWord, 1)
  3. For each dequeued word: generate all 26×L one-letter variants
  4. Variants found in the set are neighbors: delete them (visited) and enqueue with length+1
  5. The first dequeue of endWord returns its ladder length; a drained queue returns 0

Time complexity: O(N × L²) where N = dictionary size, L = word length · Space complexity: O(N × L)

Pseudocode

function ladderLength(beginWord, endWord, wordList):
    words = set(wordList)
    if endWord not in words:
        return ____
    
    queue = [(beginWord, 1)]
    while queue not empty:
        (word, steps) = queue.pop_front()
        if word == ____:
            return ____
        for each position i, each letter ch:
            nxt = word with position i set to ch
            if nxt in words:
                words.____(nxt)
                queue.push((nxt, steps + ____))
    
    return 0

Hints

  • A ladder can only end on a dictionary word, what if endWord is missing?
  • BFS's first arrival at the target is the answer, return what?
  • Discovered words must never re-enter the search, what does the set do?
  • Each hop down the ladder adds how much to the length?

Complexity questions

With N dictionary words of length L, what does the BFS cost?

O(N × L²): each word generates 26L variants, each built and hashed in O(L). Each of up to N words is processed once: 26L candidate strings, each costing O(L) to build and hash → O(N·26·L²) = O(N·L²). The pairwise-comparison approach is O(N²·L), far worse for big dictionaries.

What is the space complexity?

O(N × L): the word set and the queue hold up to N words of length L. The set starts with all N words; the queue can briefly hold most of them. Each word occupies O(L).

DFS would eventually find cog too. Why is its answer untrustworthy here?

DFS commits to one branch and may find a LONG ladder first: it explores by depth, not by distance, so its first arrival proves nothing about minimality. DFS might wander hit→hot→lot→log→dog→cog (6 words) and report it. Only BFS's wave discipline guarantees that the first touch of endWord used a minimum number of steps.

A lock shows 4 dials (0-9); one move turns a dial ±1; some states are forbidden. 'Minimum moves from 0000 to a target?', what is this?

Word Ladder in disguise: states are nodes, single-dial turns are edges, forbidden states are missing dictionary words, BFS from 0000. That's LeetCode's 'Open the Lock', structurally identical: implicit state graph + shortest path + BFS with a visited set. Recognize the shape once, solve the whole family.

Check your understanding of Word Ladder

Where is the graph in this problem?

Words are NODES; an edge joins two words that differ by exactly one letter. The costume drops: 'hit'—'hot' differ in one letter, so they're neighbors. A transformation sequence is a PATH through this word graph. Spotting hidden graphs like this is the last skill of the track.

The problem says SHORTEST transformation. Which tool does that word demand?

BFS: its waves visit all ladders of length k before any of length k+1, so the first arrival is provably shortest. SHORTEST in an unweighted graph = BFS, every time. DFS finds A path, possibly a terrible one; BFS's distance ordering guarantees the first time we touch endWord is via a minimum ladder.

How do we find a word's neighbors efficiently?

For each position, try all 26 letters and check membership in a word SET, 26 × length lookups instead of scanning the whole dictionary. Comparing against all N dictionary words costs O(N·L) per word. Generating the 26·L one-letter variants and testing each against a hash set costs O(26·L·L), independent of dictionary size. For large dictionaries this is the difference between passing and timing out.

What plays the visited-set role here?

REMOVING each discovered word from the dictionary set. A removed word can never be re-queued. Deleting on discovery is visited-marking with a bonus: it also shrinks future neighbor searches. Without it, hit → hot → hit → hot ... loops forever.

wordList = ["hot","dot","dog","lot","log"] (no "cog"). What's the answer for hit → cog, and where's the shortcut?

0, and we can return it immediately: if endWord isn't in the dictionary, no ladder can ever end there. Every intermediate AND the final word must be dictionary words. A missing endWord makes the answer 0 before any search: a one-line early exit worth writing.

Related problems

Keep practising