Skip to main content

127. Word Ladder

hardAsked at DoorDash

Find the shortest transformation sequence from beginWord to endWord, changing one letter at a time and using only words in the dictionary. DoorDash leans on this for the BFS-on-implicit-graph pattern — they want to see the wildcard-key optimization on the adjacency lookup.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in DoorDash loops.

  • Glassdoor (2026-Q1)— DoorDash SWE onsite reports cite Word Ladder as a recurring BFS-on-graph question.
  • Blind (2025-12)— DoorDash new-grad reports note the wildcard-pattern trick as the actual interview 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 si for 1 <= i <= k is in wordList, and 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 <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • beginWord, endWord, and wordList[i] consist of lowercase English letters.

Examples

Example 1

Input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output
5

Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> "cog", which is 5 words long.

Example 2

Input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output
0

Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Approaches

1. BFS with wildcard buckets (optimal)

Pre-build a map from wildcard pattern (h*t, *ot, ho*) to list of matching words. BFS from beginWord; for each word, enumerate its L wildcards and visit all neighbors in those buckets.

Time
O(N * L^2)
Space
O(N * L^2)
function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  const L = beginWord.length;
  const buckets = new Map();
  for (const word of wordSet) {
    for (let i = 0; i < L; i++) {
      const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
      if (!buckets.has(pattern)) buckets.set(pattern, []);
      buckets.get(pattern).push(word);
    }
  }
  const visited = new Set([beginWord]);
  let queue = [beginWord];
  let level = 1;
  while (queue.length) {
    const next = [];
    for (const word of queue) {
      if (word === endWord) return level;
      for (let i = 0; i < L; i++) {
        const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
        for (const neighbor of buckets.get(pattern) || []) {
          if (!visited.has(neighbor)) {
            visited.add(neighbor);
            next.push(neighbor);
          }
        }
        buckets.set(pattern, []);
      }
    }
    queue = next;
    level++;
  }
  return 0;
}

Tradeoff: DoorDash's preferred answer. Wildcard buckets reduce the neighbor lookup from O(N*L) per word to O(L) per word. Bidirectional BFS can cut it further but the wildcard version usually suffices.

2. BFS with naive neighbor enumeration

BFS; for each word, generate all L*26 possible one-letter mutations and check membership in the dictionary set.

Time
O(N * L * 26)
Space
O(N)
function ladderLengthNaive(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  const visited = new Set([beginWord]);
  let queue = [beginWord];
  let level = 1;
  while (queue.length) {
    const next = [];
    for (const word of queue) {
      if (word === endWord) return level;
      for (let i = 0; i < word.length; i++) {
        for (let c = 97; c <= 122; c++) {
          const ch = String.fromCharCode(c);
          if (ch === word[i]) continue;
          const neighbor = word.slice(0, i) + ch + word.slice(i + 1);
          if (wordSet.has(neighbor) && !visited.has(neighbor)) {
            visited.add(neighbor);
            next.push(neighbor);
          }
        }
      }
    }
    queue = next;
    level++;
  }
  return 0;
}

Tradeoff: Easier to write under stress. Works fine for the given constraints (N=5000, L=10). Mention the wildcard speedup verbally if you don't have time to code it.

DoorDash-specific tips

DoorDash interviewers grade specifically on whether you spot the WILDCARD-BUCKET preprocessing. State 'I'll bucket words by wildcard patterns to make neighbor lookup O(L) instead of O(N*L)' BEFORE coding. The naive version still passes the constraints but won't impress.

Common mistakes

  • Forgetting to check endWord is in the dictionary — return 0 if not.
  • Counting words instead of edges (level is the count, off-by-one if you start at 0).
  • Using DFS — wrong shape; the question asks for SHORTEST path.

Follow-up questions

An interviewer at DoorDash may pivot to one of these next:

  • Word Ladder II (LC 126) — return all shortest sequences.
  • Open the Lock (LC 752) — BFS on 4-digit lock states.
  • Minimum Genetic Mutation (LC 433) — same shape, different alphabet.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why BFS, not DFS?

BFS guarantees the shortest path from beginWord on each level. DFS would visit deeper paths first and not find the minimum without explicit shortest-tracking.

What's bidirectional BFS?

Search from both beginWord and endWord, alternating sides; they meet at the midpoint. Roughly sqrt() the work. DoorDash sometimes asks this as a follow-up.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Word Ladder and other DoorDash interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →