Word Ladder
Find the fewest words needed to turn one word into another by changing one letter at a time through a dictionary. A shortest-path problem solved with breadth-first search. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given two words, beginWord and endWord, and a dictionary wordList. A ladder is a sequence of words that starts with beginWord and ends with endWord, where:
- each word differs from the one before it in exactly one letter position, and
- every word after
beginWordis inwordList.
Return the number of words in the shortest ladder, counting both ends. If no ladder exists, return 0.
beginWord does not have to be in wordList, but endWord does, or no ladder can reach it.
Example 1
- Input
- beginWord = "cold", endWord = "warm", wordList = ["cord", "card", "ward", "warm", "worm", "word"]
- Output
- 5
One shortest ladder is cold → cord → card → ward → warm. Going through "word" and "worm" is also five words.
Example 2
- Input
- beginWord = "lead", endWord = "gold", wordList = ["load", "goad", "gold"]
- Output
- 4
lead → load → goad → gold.
Example 3
- Input
- beginWord = "dog", endWord = "cat", wordList = ["dot", "cot"]
- Output
- 0
"cat" is not in the word list, so no ladder can end there.
Constraints
- 1 ≤ beginWord.length ≤ 10
- endWord.length == beginWord.length, and every word in wordList has that length
- 1 ≤ wordList.length ≤ 2 × 10⁴
- All words are lowercase English letters, and beginWord ≠ endWord
- The words in wordList are distinct.
Practice
Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Word Ladder in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Word Ladder
Pattern: Breadth-first search on an implicit graph
Picture every word as a node, with an edge between two words that differ in exactly one letter. A ladder is then a path, and the shortest ladder is the shortest path in an unweighted graph. Unweighted shortest path means BFS: it explores words in order of distance, so the first time it reaches endWord is guaranteed to be the shortest.
The graph is never given to you, so the real work is finding neighbors fast. Comparing a word against the whole dictionary is O(N · L) per word. Instead, generate candidates: for each position, try all 26 letters and keep the ones that are in a set of dictionary words. That's 26 · L lookups per word, independent of the dictionary size.
BFS from one end grows fast, since each level fans out. Searching from both ends and always expanding the smaller frontier keeps both searches shallow, and they meet in the middle.
Approach 1: BFS with pairwise comparison
Run BFS from beginWord. To find neighbors, compare the current word against every unvisited dictionary word letter by letter. Correct, but with 2 × 10⁴ words that is up to 4 × 10⁸ character comparisons.
Time O(N² · L) · Space O(N)
Approach 2: BFS with letter substitution
Put the dictionary in a set. For each word popped from the queue, try every letter at every position. Each candidate in the set is a neighbor: add it to the queue with distance + 1 and remove it from the set so it is never visited twice. Return the distance when you generate endWord.
Time O(N · L² · 26) · Space O(N · L)
Approach 3: Bidirectional BFS
Keep two frontier sets, one grown from beginWord and one from endWord, plus the set of words not yet visited.
- If
endWordisn't in the dictionary, return 0. - Each round, expand the smaller frontier by one step using letter substitution.
- If a generated word is in the other frontier, the searches have met: return the number of steps taken so far plus one.
- Otherwise, collect unvisited words as the next frontier and remove them from the unvisited set.
- If a frontier ever becomes empty, there's no ladder: return 0.
The worst case matches one-directional BFS, but in practice each side only explores about half the depth, which is far fewer words.
Time O(N · L² · 26) · Space O(N · L)
| Approach | Time | Space |
|---|---|---|
| BFS with pairwise comparison | O(N² · L) | O(N) |
| BFS with letter substitution | O(N · L² · 26) | O(N · L) |
| Bidirectional BFS | O(N · L² · 26) | O(N · L) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Word Ladder solution in Python
def ladder_length(begin_word: str, end_word: str, word_list: list[str]) -> int:
unvisited = set(word_list)
if end_word not in unvisited:
return 0
unvisited.discard(begin_word)
unvisited.discard(end_word)
front, back = {begin_word}, {end_word}
length = 1
letters = "abcdefghijklmnopqrstuvwxyz"
while front and back:
if len(front) > len(back):
front, back = back, front
next_front = set()
for word in front:
for i in range(len(word)):
for ch in letters:
if ch == word[i]:
continue
candidate = word[:i] + ch + word[i + 1:]
if candidate in back:
return length + 1
if candidate in unvisited:
unvisited.remove(candidate)
next_front.add(candidate)
front = next_front
length += 1
return 0Word Ladder solution in JavaScript
function ladderLength(beginWord, endWord, wordList) {
const unvisited = new Set(wordList);
if (!unvisited.has(endWord)) return 0;
unvisited.delete(beginWord);
unvisited.delete(endWord);
let front = new Set([beginWord]);
let back = new Set([endWord]);
let length = 1;
const letters = 'abcdefghijklmnopqrstuvwxyz';
while (front.size && back.size) {
if (front.size > back.size) [front, back] = [back, front];
const nextFront = new Set();
for (const word of front) {
for (let i = 0; i < word.length; i++) {
for (const ch of letters) {
if (ch === word[i]) continue;
const candidate = word.slice(0, i) + ch + word.slice(i + 1);
if (back.has(candidate)) return length + 1;
if (unvisited.has(candidate)) {
unvisited.delete(candidate);
nextFront.add(candidate);
}
}
}
}
front = nextFront;
length++;
}
return 0;
}Common mistakes
- Returning the number of steps (edges) instead of the number of words. A one-change ladder like abc → abd has 2 words.
- Marking words visited when they are popped instead of when they are enqueued, which lets the same word into the queue many times.
- Using DFS, which finds a ladder but not necessarily the shortest one, and can explore exponentially many paths.
- Not checking up front whether endWord is in the dictionary.
- Rebuilding the dictionary as a list and checking membership with a linear scan, which brings back the O(N) cost per lookup.
What interviewers look for
Name the reduction first: "words are nodes, one-letter changes are edges, and I want the shortest path, so BFS." That sentence carries most of the signal. Then talk about how you find neighbors, because that's the part that decides whether it runs in time. Compare the 26 · L substitution approach with scanning the dictionary, and say when each is better (substitution wins when N is large relative to 26 · L).
Bidirectional BFS is a strong finish. Mention it and why expanding the smaller side helps, even if you code the one-directional version first.
Follow-up questions
How would you return every shortest ladder, not just the length?
Run BFS level by level and record, for each word, all parents one level closer to the start, never adding words seen at earlier levels. Once endWord is reached, stop after finishing that level and backtrack from endWord through the parent lists with DFS to build every path.
What if the dictionary is huge and words are long?
Precompute wildcard buckets: map patterns like "c*ld" to the words that match them. Neighbors of a word are the union of its L buckets. This trades memory for not regenerating 26 · L candidates per word, and it works well when many queries share one dictionary.
What if changing some letters costs more than others?
The graph becomes weighted, so BFS no longer gives shortest paths. Use Dijkstra’s algorithm with a priority queue, or A* with a heuristic such as the number of mismatched positions times the minimum change cost.
Companies that ask Word Ladder
Word Ladder is tagged by 126 companies in our interview dataset. The score shows how often it comes up at each company.
- Mixi100%
- Blackhawk Network100%
- Transunion100%
- Geotab100%
- Reddit100%
- Navan100%
- Workspan98%
- Momentiveai95%
- Yelp94.2%
- Credit Karma94%
- Snap93.7%
- Fivetran91%
- Nasa Jpl87%
- Tata Consultancy Services84%
- Tenstorrent84%
- Argo Ai83%
- And Digital82%
- Arrow Electronics81%
- Icims81%
- LinkedIn79%
- Loom79%
- Testlio79%
- Ellucian78%
- The Trade Desk78%
and 102 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required