Word Ladder

Given beginWord, endWord, and a word list, return the length of the shortest transformation sequence from beginWord to endWord such that:

• You may change exactly one letter at a time.
• Each word entered by a change, including endWord, must exist in the word list.

Return 0 if no such sequence exists.

Why this is worth learning

Words are vertices; changing one position is an unweighted edge. Wildcard buckets are an adjacency index, not an alternative distance metric. The answer counts words, so the start has distance 1.

Before coding: one-minute experiment

For hit->hot->dot->dog->cog, what is the returned length? Why must cog be in the dictionary even though hit need not be?

Function signature

func LadderLength(beginWord, endWord string, wordList []string) int

Inputs / outputs

• beginWord, endWord: lowercase words of the same length.
• wordList: allowed changed-to words, including the target.
• Return: length of the shortest sequence, or 0.

Example

begin = "hit", end = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5 (hit -> hot -> dot -> dog -> cog)

Constraints

• 1 <= len(wordList) <= 50_000
• word length <= 10

Core idea (near-solution)

A baseline compares every dictionary word with every other to create one-letter edges. Many comparisons repeat the same information. A pattern such as c*rd groups words that agree in every position except one, so wildcard buckets index candidate neighbors without a full pairwise graph. Search those legal edges in increasing transformation count with a FIFO queue. First discovery gives the fewest changes because every edge is one change. The reported answer counts words, so the source begins at 1 rather than 0; the changed-to destination must also be allowed.

Invariant: BFS explores words in increasing transformation distance.

Algorithm (step-by-step)

1. Put all words into a set; if endWord not present, return 0.
2. Build a map from wildcard pattern to words (e.g., h*t -> hot, hat).
3. BFS from beginWord. For each word, generate its patterns and enqueue unseen neighbors.
4. The first time you reach endWord, return the distance.

Correctness sketch

FIFO processing ensures all words at distance d are processed before any newly discovered word at distance d+1. Every legal one-letter neighbor shares a wildcard pattern with the current word, and each bucket contains only such neighbors (apart from the current word itself). Thus all shorter paths would have been explored before a word is first enqueued. Clearing a bucket after its first expansion is safe: all its words have then been discovered at distance at most the current distance plus one; a later use cannot improve them. The first dequeue of endWord gives the shortest number of words, and exhaustion proves it unreachable.

Trace (hand walkthrough)

Example input:
begin = "hit", end = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5 (hit -> hot -> dot -> dog -> cog)

Walk:
- level 1: hit -> hot
- level 2: hot -> dot, lot
- level 3: dot->dog, lot->log
- level 4: dog/log -> cog -> length 5

Pitfalls to avoid

• Not marking visited on enqueue (causes repeated work).
• Forgetting to check if endWord is in the dictionary.

Debugging lens

Separate edge count from word count. Mark on enqueue and clear only a fully expanded wildcard bucket. When begin equals end, preserve the existing membership check: return 1 only if that word is in the list, otherwise 0.

Complexity

Let N include the start when it is added and L be the common byte length. Expected time O(N L^2): each of N L patterns requires constructing/hashing a length-L string, plus O(N L) bucket entries scanned once. Auxiliary space is O(N L^2) bytes in the worst case for distinct pattern strings, plus O(N L) word references; treating string keys as unit-size gives the coarser O(N L) entry count.

Implementation notes (Go)

• Precompute wildcard pattern buckets to find candidate buckets; string construction, hashing, and scanning a bucket are not O(1) total work.
• Mark words visited on enqueue to avoid duplicates.

Contract precision

All words must have the same positive length and contain lowercase English letters. The end word must be in wordList. Return values count vertices, not transformations.

Reconstruction checkpoint

begin="cold", end="ward", dictionary=["cord","card","ward"]. Give the answer and its unit. What changes if "ward" is removed while the first two words remain?

Return to Graph BFS · Module quiz