Word Ladder
Find the shortest sequence of one-letter changes from one word to another with BFS, visiting each word once, level by level.
Problem Understanding
Word Ladder: transform beginWord into endWord by changing one letter at a time, where every intermediate word must be in wordList. Return the number of words in the shortest such sequence, counting both ends, or 0 if none exists.
Example: hit → hot → dot → dog → cog has 5 words, so ladderLength("hit", "cog", [hot, dot, dog, lot, log, cog]) returns 5.
The Intuition: A Shortest Path in a Word Graph
Picture every word as a node, with an edge between two words that differ in exactly one letter. A ladder is a path, and the shortest ladder is the shortest path. Every edge has the same cost, so breadth-first search finds it.
- If
endWordis not in the list, return 0. - Start the queue with
beginWordat length 1. - Process one level at a time. For each word, try every one-letter change; any change still in the word set is removed from the set (visited) and queued.
- After each level, add 1 to the length. The first time
endWordis popped, return the length.
Removing words when they are queued is what keeps each word from being visited twice.
Interactive Walkthrough
Each row is one BFS level: the words first reached by a sequence of that length. The word being expanded is filled, the words it queues are shaded, and the end word turns green when it is reached.
Dry Run Table
Input: hit → cog, list [hot, dot, dog, lot, log, cog]
| Length | Words at this level |
|---|---|
| 1 | hit |
| 2 | hot |
| 3 | dot, lot |
| 4 | dog, log |
| 5 | cog |
cog is reached at length 5.
The Solution Template
Level-order BFS with a word set. C has no built-in hash set, so its snippet compares each word against the list directly (O(N² · L)), with a visited array.
Word Ladder Code
1var ladderLength = function(beginWord, endWord, wordList) {2 const words = new Set(wordList);3 if (!words.has(endWord)) return 0;4 let queue = [beginWord];5 let length = 1;6 while (queue.length) {7 const next = [];8 for (const word of queue) {9 if (word === endWord) return length;10 for (let i = 0; i < word.length; i++) {11 for (let c = 97; c <= 122; c++) {12 const nxt = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);13 if (words.delete(nxt)) next.push(nxt);14 }15 }16 }17 queue = next;18 length++;19 }20 return 0;21};
Edge Cases & Common Mistakes
- endWord not in the list: return 0 before searching.
- Counting edges instead of words: the answer counts words, so
beginWordalone has length 1. - Marking visited on pop instead of on push: the same word can be queued many times in one level; remove it from the set when it is queued.
- Using DFS: DFS finds a ladder, not necessarily the shortest; BFS levels guarantee the minimum.
Summary
Words are nodes and one-letter changes are edges, so the shortest ladder is a BFS shortest path. Queue beginWord, expand each level by trying every letter at every position, remove words from the set as they are queued, and return the level count when endWord is reached, or 0.
More practice: DSA interview questions with answers · patterns cheat sheet