Word Ladder II
Return every shortest sequence of one-letter changes that turns one word into another through a dictionary. BFS to find the shortest distance, then rebuild only the paths that achieve it. 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 all of the shortest ladders, each as a list of words from beginWord to endWord. If no ladder exists, return an empty list.
beginWord does not have to be in wordList. The ladders can be returned in any order, but the words inside each ladder must be in sequence.
Example 1
- Input
- beginWord = "pin", endWord = "bat", wordList = ["pan", "ban", "bat", "pit", "pat", "bin"]
- Output
- [["pin","bin","ban","bat"], ["pin","pan","ban","bat"], ["pin","pan","pat","bat"], ["pin","pit","pat","bat"]]
Three letters differ, so every ladder needs at least three changes. There are four ways to make them through dictionary words.
Example 2
- Input
- beginWord = "lead", endWord = "gold", wordList = ["load", "goad", "gold", "lend", "lold", "bold", "lead"]
- Output
- [["lead","load","goad","gold"], ["lead","load","lold","gold"]]
"bold" and "lend" are in the dictionary but are not on any shortest ladder.
Example 3
- Input
- beginWord = "pin", endWord = "bat", wordList = ["pan", "ban", "pit", "pat", "bin"]
- Output
- []
"bat" is not in the dictionary, so no ladder can end there.
Constraints
- 1 ≤ beginWord.length ≤ 5
- endWord.length == beginWord.length, and every word in wordList has that length
- 1 ≤ wordList.length ≤ 3125, and its words are distinct
- All words contain only lowercase English letters.
- beginWord != endWord
Practice
Runs 13 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Word Ladder II 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 II
Pattern: BFS layers + backtracking over a parent DAG
Words are nodes, and two words are connected when they differ in one letter. "Shortest ladder" means shortest path, so breadth-first search is the tool. Word Ladder I only needs the distance; here you need every path of that length.
The trap is trying to carry full paths through the BFS or running DFS over the whole graph: the number of partial paths explodes, and most of them are not shortest. Instead, split the work:
- BFS by layers from
beginWord. When a word in the next layer is first discovered, record every word in the current layer that reaches it as a parent. Only edges from layerdto layerd + 1are kept, so the parent links form a DAG that contains exactly the shortest paths. - Stop after the layer that contains
endWord. - Backtrack from
endWordthrough the parent links tobeginWord, then reverse each path.
The important detail is to remove a whole layer from the dictionary only after that layer is finished. Removing words as soon as they are discovered would drop the second parent of a word that two words in the same layer both reach.
Approach 1: DFS over all ladders
Depth-first search from beginWord, keeping the current path and a visited set, recording every ladder that reaches endWord and keeping only the shortest ones. Correct, but it explores every simple path in the graph, which is exponential on dense dictionaries.
Time Exponential · Space O(n · L)
Approach 2: BFS carrying full paths
Put whole paths in the queue instead of single words, extend each path by one word per step, and stop after the level that reaches endWord. Simpler to write than parent links, but every partial path is stored, so memory and time grow with the number of partial paths rather than the number of words.
Time O(number of partial paths · L · 26) · Space O(number of partial paths · L)
Approach 3: Layered BFS with a parent map, then backtrack
- Put the dictionary in a set. If
endWordis missing, return[]. - BFS one layer at a time. Remove the current layer's words from the set, then for each word try every one-letter change; when the result is in the set, add the current word to that result's parent list and put the result in the next layer.
- Once a layer contains
endWord, stop. - DFS from
endWordalong parent lists tobeginWordand output each path reversed.
The BFS is O(n · L · 26) for n words of length L. The backtracking is proportional to the size of the output.
Time O(n · L · 26 + output size) · Space O(n · L + output size)
| Approach | Time | Space |
|---|---|---|
| DFS over all ladders | Exponential | O(n · L) |
| BFS carrying full paths | O(number of partial paths · L · 26) | O(number of partial paths · L) |
| Layered BFS with a parent map, then backtrack | O(n · L · 26 + output size) | O(n · L + output size) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Word Ladder II solution in Python
from collections import defaultdict
def find_ladders(begin_word: str, end_word: str, word_list: list[str]) -> list[list[str]]:
words = set(word_list)
if end_word not in words:
return []
parents = defaultdict(list)
layer = {begin_word}
found = False
while layer and not found:
words -= layer # remove the whole layer only after it is complete
next_layer = set()
for word in layer:
for i in range(len(word)):
for ch in "abcdefghijklmnopqrstuvwxyz":
cand = word[:i] + ch + word[i + 1:]
if cand in words:
parents[cand].append(word)
next_layer.add(cand)
found = end_word in next_layer
layer = next_layer
if not found:
return []
ladders = []
path = [end_word]
def backtrack(word: str) -> None:
if word == begin_word:
ladders.append(path[::-1])
return
for parent in parents[word]:
path.append(parent)
backtrack(parent)
path.pop()
backtrack(end_word)
return laddersWord Ladder II solution in JavaScript
function findLadders(beginWord, endWord, wordList) {
const words = new Set(wordList);
if (!words.has(endWord)) return [];
const parents = new Map();
let layer = new Set([beginWord]);
let found = false;
while (layer.size && !found) {
for (const w of layer) words.delete(w); // remove the whole layer only after it is complete
const next = new Set();
for (const word of layer) {
for (let i = 0; i < word.length; i++) {
for (let c = 97; c <= 122; c++) {
const cand = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
if (!words.has(cand)) continue;
if (!parents.has(cand)) parents.set(cand, []);
parents.get(cand).push(word);
next.add(cand);
}
}
}
found = next.has(endWord);
layer = next;
}
if (!found) return [];
const ladders = [];
const path = [endWord];
const backtrack = (word) => {
if (word === beginWord) {
ladders.push([...path].reverse());
return;
}
for (const parent of parents.get(word)) {
path.push(parent);
backtrack(parent);
path.pop();
}
};
backtrack(endWord);
return ladders;
}Common mistakes
- Removing a word from the dictionary as soon as it is discovered, which loses other same-layer parents and therefore some shortest ladders.
- Continuing the BFS after the layer that reaches endWord, which adds longer paths.
- Running a DFS over the whole graph, which times out on dense dictionaries like every 5-letter word over a small alphabet.
- Forgetting to return [] when endWord is not in the dictionary.
- Building ladders from beginWord forward through children instead of backward through parents, which follows dead branches that never reach endWord.
What interviewers look for
Say up front that you will reuse Word Ladder I: "BFS gives the shortest distance; I'll also record how I reached each word so I can rebuild the paths." Then explain why you keep parents layer by layer. Interviewers listen for the "remove the whole layer after processing it" detail, because it is the bug most candidates hit.
Be clear that the output can be large, so the goal is to make the search linear in the dictionary and let the backtracking cost only what the answer costs.
Follow-up questions
How would bidirectional BFS help?
Grow layers from both ends, always expanding the smaller frontier, until they meet. This shrinks the explored area a lot on large dictionaries. You still record parent links (flipping direction for the backward side) and stop at the first layer where the frontiers touch.
How would you only count the shortest ladders?
During the layered BFS, keep ways[word] = sum of ways[parent] over its parents, starting from ways[beginWord] = 1. The answer is ways[endWord], and you never build the paths.
How do you find neighbors faster when words are long?
Precompute wildcard patterns: map each word to keys like "h*t" for every position. Words that share a key are neighbors, so lookups no longer try all 26 letters. This also helps when the alphabet is large.
Companies that ask Word Ladder II
Word Ladder II is tagged by 97 companies in our interview dataset. The score shows how often it comes up at each company.
- Intercom100%
- Ciklum98%
- Blizzard Entertainment98%
- Telstra95%
- Yelp94.2%
- Carvana94%
- Latitude Ai91%
- Procore Technologies87%
- Square Enix86%
- Plaid85%
- Sortly83%
- Goto83%
- Culture Amp82%
- Acquia81%
- Thought Machine79%
- Solo Funds78%
- Liberty It78%
- Nebius78%
- Thales76%
- 1password76%
- Vercel76%
- Gemini75%
- Tempus75%
- Okta70.8%
and 73 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