127. Word Ladder
hardAsked at AirbnbGiven begin/end words and a word list, find the shortest transformation sequence (one letter at a time, each step in the list). Airbnb asks this to test BFS on implicit graphs plus the wildcard-bucket trick.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Airbnb loops.
- Glassdoor (2026-Q1)— Airbnb senior onsite reports include this as a recurring graph hard.
- Blind (2025-11)— Mentioned in Airbnb backend interview reports.
Problem
A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence beginWord -> s1 -> s2 -> ... -> sk such that every adjacent pair of words differs by a single letter and every word (except possibly beginWord) is in wordList. Return the number of words in the shortest sequence, or 0 if no such sequence exists.
Constraints
1 <= beginWord.length <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthAll words consist of lowercase English letters.All the words in wordList are unique.
Examples
Example 1
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]5Example 2
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]0Approaches
1. Naive BFS — compare every pair
BFS from beginWord. For each frontier word, scan the list for one-letter neighbors.
- Time
- O(N^2 * L)
- Space
- O(N * L)
function ladderLengthNaive(beginWord, endWord, wordList) {
const dict = new Set(wordList);
if (!dict.has(endWord)) return 0;
function differsByOne(a, b) {
let d = 0;
for (let i = 0; i < a.length; i++) if (a[i] !== b[i]) d++;
return d === 1;
}
const visited = new Set([beginWord]);
let queue = [beginWord], steps = 1;
while (queue.length) {
const next = [];
for (const word of queue) {
if (word === endWord) return steps;
for (const w of dict) {
if (!visited.has(w) && differsByOne(word, w)) {
visited.add(w);
next.push(w);
}
}
}
queue = next;
steps++;
}
return 0;
}Tradeoff: Easy to write but N * L per frontier word is too slow at 5000 words. Mention before pivoting to wildcard buckets.
2. BFS with wildcard buckets (optimal)
Preprocess each word into L wildcard patterns. Two words are neighbors iff they share a pattern.
- Time
- O(N * L^2)
- Space
- O(N * L^2)
function ladderLength(beginWord, endWord, wordList) {
const dict = new Set(wordList);
if (!dict.has(endWord)) return 0;
const L = beginWord.length;
const buckets = new Map();
for (const w of wordList) {
for (let i = 0; i < L; i++) {
const key = w.slice(0, i) + '*' + w.slice(i + 1);
if (!buckets.has(key)) buckets.set(key, []);
buckets.get(key).push(w);
}
}
const visited = new Set([beginWord]);
let queue = [beginWord], steps = 1;
while (queue.length) {
const next = [];
for (const word of queue) {
if (word === endWord) return steps;
for (let i = 0; i < L; i++) {
const key = word.slice(0, i) + '*' + word.slice(i + 1);
for (const neighbor of buckets.get(key) || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
next.push(neighbor);
}
}
}
}
queue = next;
steps++;
}
return 0;
}Tradeoff: O(N * L^2) preprocessing + fast neighbor lookups. Works at the 5000-word constraint.
3. Bidirectional BFS
BFS from both ends, expanding the smaller frontier each step. Stop when frontiers intersect.
- Time
- O(N * L^2)
- Space
- O(N * L^2)
function ladderLengthBi(beginWord, endWord, wordList) {
const dict = new Set(wordList);
if (!dict.has(endWord)) return 0;
const L = beginWord.length;
let front = new Set([beginWord]);
let back = new Set([endWord]);
const visited = new Set([beginWord, endWord]);
let steps = 1;
while (front.size && back.size) {
if (front.size > back.size) [front, back] = [back, front];
const next = new Set();
for (const word of front) {
for (let i = 0; i < L; i++) {
for (let c = 97; c <= 122; c++) {
const cand = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
if (back.has(cand)) return steps + 1;
if (dict.has(cand) && !visited.has(cand)) {
visited.add(cand);
next.add(cand);
}
}
}
}
front = next;
steps++;
}
return 0;
}Tradeoff: Often 2-5x faster in practice. Same big-O, smaller constants because the effective search radius is halved.
Airbnb-specific tips
Airbnb's bar is reaching for the wildcard-bucket idea once you've named the naive cost. Say: 'Comparing every pair is N^2 per level. I'll preprocess each word into L wildcard patterns so neighbors share a bucket.' If you go straight to bidirectional BFS, still mention the bucket map as the underlying neighbor-lookup tool.
Common mistakes
- Forgetting to check that endWord is in the dictionary.
- Using DFS — gives wrong shortest path.
- Not visiting on the right side (mark when you enqueue, not when you dequeue) — causes duplicates.
Follow-up questions
An interviewer at Airbnb may pivot to one of these next:
- Word Ladder II (LC 126) — return all shortest sequences.
- Open the Lock (LC 752) — same BFS pattern with 4-digit wheels.
- What if the dictionary changes over time? (Precompute buckets once; update on insert/delete.)
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why BFS not Dijkstra?
All edge weights are 1; BFS is O(V + E) without log factor.
Wildcard buckets or explicit adjacency list — which is better?
Asymptotically identical. Buckets are usually fewer lines of code; explicit adjacency is more familiar to graph-textbook readers.
Free learning resources
Curated free links for this problem.
Practice these live with InterviewChamp.AI
Drill Word Ladder and other Airbnb interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →