Skip to main content

99. Word Ladder

hardAsked at Plaid

Find the shortest transformation from beginWord to endWord, changing one letter at a time, where each intermediate is in the dictionary. Plaid asks this as a BFS-shortest-path problem — the same shape as finding the minimum-hop route across their bank-rail graph.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE III onsite — bank-rail-hop variant.
  • LeetCode Discuss (2026)— Plaid BFS hard.

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
  • All words consist of lowercase English letters.

Examples

Example 1

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

Explanation: hit -> hot -> dot -> dog -> cog.

Example 2

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

Approaches

1. BFS with naive neighbor check

For each dequeued word, check every dictionary word for one-letter difference.

Time
O(N^2 * L)
Space
O(N)
// Quadratic in dict size. Slow.

Tradeoff: TLE for large dicts.

2. BFS with pattern-key buckets

Pre-build a map from patterns like 'h*t' to lists of matching words. Each BFS step looks up neighbors in O(L) per pattern.

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 patterns = new Map();
  for (const word of dict) {
    for (let i = 0; i < L; i++) {
      const p = word.slice(0, i) + '*' + word.slice(i + 1);
      if (!patterns.has(p)) patterns.set(p, []);
      patterns.get(p).push(word);
    }
  }
  const visited = new Set([beginWord]);
  let level = [beginWord], dist = 1;
  while (level.length) {
    const next = [];
    for (const word of level) {
      if (word === endWord) return dist;
      for (let i = 0; i < L; i++) {
        const p = word.slice(0, i) + '*' + word.slice(i + 1);
        for (const nb of (patterns.get(p) || [])) {
          if (!visited.has(nb)) { visited.add(nb); next.push(nb); }
        }
      }
    }
    level = next;
    dist++;
  }
  return 0;
}

Tradeoff: Pattern lookup is O(L) per character. Total work bounded by N * L^2. Pre-building patterns is the optimization.

Plaid-specific tips

Plaid grades this on whether you precompute the pattern buckets — without that, each BFS step degenerates to O(N) per word. Bonus signal: discuss bidirectional BFS as a stretch — meet in the middle for a ~2x speedup. Connect to bank-rail routing.

Common mistakes

  • Not pre-building patterns — quadratic dictionary search.
  • Forgetting to short-circuit when endWord is found.
  • Returning dist + 1 — should be dist (since we count the start word).

Follow-up questions

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

  • Word Ladder II (LC 126) — return all shortest sequences.
  • Bidirectional BFS.
  • Find the shortest sequence via specific intermediate words.

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 pattern keys?

Two words differing by exactly one letter share a pattern with '*' at that position. Bucketing by pattern lets us find all one-letter neighbors in O(L) total.

Bidirectional BFS payoff?

Each side searches half the depth, so total nodes visited is roughly sqrt(N) of the unidirectional. For long ladders, the speedup is significant.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →