25. Word Ladder

hardAsked at Figma

Find the shortest transformation sequence from beginWord to endWord, changing one letter at a time. Figma uses this to probe graph-shortest-path intuition that maps onto state transitions in their multiplayer CRDT replay engine.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Problem

A transformation sequence from beginWord to endWord using a wordList is a sequence of words where each adjacent pair differs by exactly one letter and every word (except possibly beginWord) appears in wordList. Return the length of the shortest such sequence, or 0 if no sequence exists.

Constraints

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
All words consist of lowercase English letters

Examples

Example 1

Input

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

Output

Example 2

Input

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

Output

Approaches

1. BFS comparing every pair

Build a graph by checking edit-distance between every word pair, then BFS.

Time: O(n^2 * k)
Space: O(n^2)

function ladderLength(begin, end, words) {
  // build edges by pairwise diff==1
  // BFS from begin until end found
  return 0;
}

Tradeoff:

2. BFS with wildcard buckets

Index every word under its k wildcard patterns (e.g. 'h*t', '*it', 'hi*'). BFS visits one bucket per step, expanding all one-letter neighbors in O(1) per neighbor. Reduces edge-build cost from O(n^2 k) to O(n k^2).

Time: O(n * k^2)
Space: O(n * k^2)

function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  const buckets = new Map();
  for (const w of wordList) {
    for (let i = 0; i < w.length; 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 w of queue) {
      if (w === endWord) return steps;
      for (let i = 0; i < w.length; i++) {
        const key = w.slice(0, i) + '*' + w.slice(i + 1);
        for (const nb of buckets.get(key) || []) {
          if (!visited.has(nb)) { visited.add(nb); next.push(nb); }
        }
      }
    }
    queue = next; steps++;
  }
  return 0;
}

Tradeoff:

Figma-specific tips

Figma's hard-bar grade is recognizing that wildcard bucketing is the same indexing trick used to find sibling CRDT ops with one differing axis — call out the analogy explicitly.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →