Word Ladder
You are given a start word beginWord, a target word endWord and a dictionary wordList. All words have the same length and use lowercase English letters.
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 position, and every word after beginWord appears in wordList. beginWord itself does not need to be in the list.
Return the number of words in the shortest ladder, counting both ends. If no ladder exists, return 0.
Example 1
Example 2
Example 3
Constraints
1 <= beginWord.length <= 10endWord.length == beginWord.length, and every word in wordList has that length too1 <= wordList.length <= 5000- All words consist of lowercase English letters; the words in wordList are distinct.
beginWord != endWord
Pattern Path · Graphs: Traversal · problem 137 of 169
a..z and look the result up in a set.Start simple
Build the full graph by comparing every pair of words letter by letter, then run BFS: O(n² · L) time just to build the edges.
The key idea
Treat every word as a node of a graph and connect two words when they differ in exactly one letter. Each step of a ladder is one edge, so the shortest ladder is a shortest path in an unweighted graph, which is exactly what breadth-first search finds: BFS visits words in order of their distance from beginWord, so the first time it reaches endWord the distance is minimal.
You never need to build the graph up front. For the current word, try every position and every letter a..z; each candidate that is in the dictionary set and not yet visited is a neighbour. That is 26 · L set lookups per word instead of comparing it against all n words.
Mark a word visited when you enqueue it, not when you dequeue it, so it is never queued twice. If endWord is not in the dictionary, answer 0 immediately. Each word is processed at most once, and building each candidate string costs O(L).
Complexity
- Time:
O(n · L² · 26) (n · 26 · L candidates, each built in O(L)) - Space:
O(n · L)
Python
import string
from collections import deque
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
words = set(wordList)
if endWord not in words:
return 0
queue = deque([(beginWord, 1)]) # (word, ladder length so far)
visited = {beginWord}
while queue:
word, length = queue.popleft()
if word == endWord:
return length
# Every dictionary word that differs from `word` in one position.
for i in range(len(word)):
for ch in string.ascii_lowercase:
candidate = word[:i] + ch + word[i + 1:]
if candidate in words and candidate not in visited:
visited.add(candidate)
queue.append((candidate, length + 1))
return 0
JavaScript
var ladderLength = function(beginWord, endWord, wordList) {
const words = new Set(wordList);
if (!words.has(endWord)) return 0;
const letters = "abcdefghijklmnopqrstuvwxyz";
const queue = [[beginWord, 1]]; // [word, ladder length so far]
const visited = new Set([beginWord]);
for (let head = 0; head < queue.length; head++) {
const [word, length] = queue[head];
if (word === endWord) return length;
// Every dictionary word that differs from `word` in one position.
for (let i = 0; i < word.length; i++) {
for (const ch of letters) {
const candidate = word.slice(0, i) + ch + word.slice(i + 1);
if (words.has(candidate) && !visited.has(candidate)) {
visited.add(candidate);
queue.push([candidate, length + 1]);
}
}
}
}
return 0;
};
What the interviewer is checking
The interviewer wants you to recognise an implicit graph, choose BFS for an unweighted shortest path, and generate neighbours cleverly instead of comparing all pairs.
Mistakes to avoid
- Forgetting to return 0 when
endWordis missing from the dictionary. - Counting steps (edges) instead of words; the answer includes both ends.
- Marking words visited only when dequeued, which can queue the same word many times.
- Using DFS, which finds a ladder but not necessarily the shortest.
Follow-ups to expect
- Return all shortest ladders, not just the length. (BFS layers plus parent links, then backtrack.)
- How can you speed up the search? (Bidirectional BFS from both ends.)
- What if letters can also be inserted or deleted? (Edit-distance-1 neighbours via wildcard patterns.)
In real software
Spell checkers and fuzzy search generate one-edit neighbours of a word the same way, and network tools use BFS to find the minimum number of hops between two machines.