127. Word Ladder
hardAsked at LinkedInGiven begin and end words and a dictionary, return the length of the shortest transformation sequence where each step changes one letter and produces a dictionary word. LinkedIn asks this on the BFS round — they want the wildcard-bucket preprocessing trick for O(N * L^2).
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in LinkedIn loops.
- Glassdoor (2026-Q1)— LinkedIn senior IC onsite reports list Word Ladder as a high-frequency BFS hard.
- Blind (2025-11)— LinkedIn writeups describe the wildcard-pattern bucket preprocessing as the explicit signal.
Problem
A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that: every adjacent pair of words differs by a single letter, every s_i for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList. sk == endWord. Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.
Constraints
1 <= beginWord.length <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthbeginWord, endWord, and wordList[i] consist of lowercase English letters.beginWord != endWordAll the words in wordList are unique.
Examples
Example 1
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]5Explanation: One shortest transformation sequence is hit -> hot -> dot -> dog -> cog. Length is 5.
Example 2
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]0Explanation: endWord is not in wordList, so no transformation sequence exists.
Approaches
1. BFS comparing every pair
BFS from beginWord; from each word, scan all dictionary words and add those that differ by one letter to the queue.
- Time
- O(N^2 * L) where N is wordList size, L is word length
- Space
- O(N)
function ladderLengthNaive(beginWord, endWord, wordList) {
const dict = new Set(wordList);
if (!dict.has(endWord)) return 0;
let queue = [beginWord], steps = 1;
const visited = new Set([beginWord]);
function diffByOne(a, b) {
let d = 0;
for (let i = 0; i < a.length; i++) if (a[i] !== b[i]) d++;
return d === 1;
}
while (queue.length) {
const next = [];
for (const w of queue) {
if (w === endWord) return steps;
for (const candidate of dict) {
if (!visited.has(candidate) && diffByOne(w, candidate)) {
visited.add(candidate);
next.push(candidate);
}
}
}
queue = next;
steps++;
}
return 0;
}Tradeoff: Correct but N^2 * L pair comparisons — slow at N = 5000. Mention then move to the bucket trick.
2. Bidirectional BFS with wildcard buckets (optimal)
Preprocess each word into L 'wildcard patterns' (replace each position with '*'). BFS where neighbors of word w are all words sharing any wildcard pattern with w.
- Time
- O(N * L^2)
- Space
- O(N * L)
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 pat = w.slice(0, i) + '*' + w.slice(i + 1);
if (!buckets.has(pat)) buckets.set(pat, []);
buckets.get(pat).push(w);
}
}
let queue = [beginWord], steps = 1;
const visited = new Set([beginWord]);
while (queue.length) {
const next = [];
for (const w of queue) {
if (w === endWord) return steps;
for (let i = 0; i < L; i++) {
const pat = w.slice(0, i) + '*' + w.slice(i + 1);
const neighbors = buckets.get(pat) || [];
for (const n of neighbors) {
if (!visited.has(n)) { visited.add(n); next.push(n); }
}
}
}
queue = next;
steps++;
}
return 0;
}Tradeoff: O(N * L^2) — at N = 5000 and L = 10, that's 500K ops. The wildcard bucket converts 'find all words differing by one letter' from O(N * L) per word to O(L^2) per word (L bucket lookups, each returning <= some bound of words on average).
LinkedIn-specific tips
LinkedIn interviewers grade explicitly on whether you reach for the wildcard-bucket optimization. Articulate: 'Naive BFS does N^2 * L comparisons. I can preprocess each word into L wildcard patterns — words that share a pattern differ by exactly one letter. Then BFS lookups become O(L) per neighbor expansion.' That sentence is the entire optimization. Be ready for the II follow-up (return all shortest paths, not just length).
Common mistakes
- Doing pairwise comparison (the naive version) — passes small cases but TLEs at N = 5000.
- Forgetting to check endWord is IN wordList — must return 0 immediately if not.
- Counting the start word as step 0 instead of step 1 — returns length - 1.
Follow-up questions
An interviewer at LinkedIn may pivot to one of these next:
- Word Ladder II (LC 126) — return all shortest sequences.
- Could you use bidirectional BFS to further cut the search? (Yes — alternate from both ends.)
- What if the alphabet were larger (Unicode)? (Bucket approach still works; comparison approach doesn't.)
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why do wildcard buckets help?
Because two words differ by one letter iff they share a wildcard pattern. Preprocessing buckets lets you find all neighbors in O(L) instead of O(N * L). For N = 5000 and L = 10, that's a 5000x speedup per word.
Is bidirectional BFS worth it?
Yes for the optimal solution — search from both ends and stop when the frontiers meet. Cuts the worst-case search from O(b^d) to O(b^(d/2)), where b is branching factor and d is path length.
Free learning resources
Curated free links for this problem.
Practice these live with InterviewChamp.AI
Drill Word Ladder and other LinkedIn interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →