Skip to main content

127. Word Ladder

hardAsked at Pinterest

Word Ladder is Pinterest's canonical BFS-on-implicit-graph problem: given a start word, end word, and word list, find the shortest transformation sequence changing one letter at a time. The interviewer wants the wildcard-bucket BFS optimization, not naive pairwise edge construction.

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

Source citations

Public interview reports confirming this problem appears in Pinterest loops.

  • Glassdoor (2026-Q1)— Pinterest L5 onsite reports cite Word Ladder as the hard BFS round.
  • LeetCode Pinterest tag (2026-Q1)— On the Pinterest company-tagged problem list.

Problem

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words such that adjacent words differ by exactly one letter and every word in the sequence is in wordList (note that beginWord need not be in wordList). Return the number of words in the shortest transformation sequence, or 0 if no sequence exists.

Constraints

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • All words in wordList are unique.
  • 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 (length 5).

Example 2

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

Explanation: endWord not in wordList.

Approaches

1. Pairwise edge BFS (brute force)

Build an adjacency list by comparing every word to every other word. BFS from beginWord.

Time
O(N^2 * L)
Space
O(N^2)
function ladderLengthBrute(beginWord, endWord, wordList) {
  const words = new Set(wordList);
  if (!words.has(endWord)) return 0;
  const all = [beginWord, ...wordList];
  function diffOne(a, b) {
    let diff = 0;
    for (let i = 0; i < a.length; i++) if (a[i] !== b[i]) diff += 1;
    return diff === 1;
  }
  const adj = new Map();
  for (let i = 0; i < all.length; i++) {
    for (let j = i + 1; j < all.length; j++) {
      if (diffOne(all[i], all[j])) {
        if (!adj.has(all[i])) adj.set(all[i], []);
        if (!adj.has(all[j])) adj.set(all[j], []);
        adj.get(all[i]).push(all[j]);
        adj.get(all[j]).push(all[i]);
      }
    }
  }
  const q = [[beginWord, 1]];
  const seen = new Set([beginWord]);
  while (q.length) {
    const [w, d] = q.shift();
    if (w === endWord) return d;
    for (const next of adj.get(w) || []) {
      if (!seen.has(next)) { seen.add(next); q.push([next, d + 1]); }
    }
  }
  return 0;
}

Tradeoff: O(N^2) pairwise checks. At N=5000 that's 25M comparisons — borderline. Anchor with this, then move.

2. Wildcard-bucket BFS (optimal)

Build a bucket map: for each word, generate L wildcard patterns ('h*t', 'ho*', '*ot'). Words sharing a pattern are one edit apart. BFS using wildcards as virtual graph nodes.

Time
O(N * L^2)
Space
O(N * L)
function ladderLength(beginWord, endWord, wordList) {
  const words = new Set(wordList);
  if (!words.has(endWord)) return 0;
  const L = beginWord.length;
  const buckets = new Map();
  function bucketize(word) {
    for (let i = 0; i < L; i++) {
      const key = word.slice(0, i) + '*' + word.slice(i + 1);
      if (!buckets.has(key)) buckets.set(key, []);
      buckets.get(key).push(word);
    }
  }
  for (const w of [beginWord, ...wordList]) bucketize(w);
  const q = [[beginWord, 1]];
  const seen = new Set([beginWord]);
  let head = 0;
  while (head < q.length) {
    const [w, d] = q[head++];
    if (w === endWord) return d;
    for (let i = 0; i < L; i++) {
      const key = w.slice(0, i) + '*' + w.slice(i + 1);
      for (const next of buckets.get(key) || []) {
        if (seen.has(next)) continue;
        seen.add(next);
        q.push([next, d + 1]);
      }
      buckets.set(key, []); // prune to avoid revisiting through the same wildcard
    }
  }
  return 0;
}

Tradeoff: O(N * L^2) — strictly better than pairwise N^2 when L << N. Wildcards turn 'find all words one-edit-away' from an O(N) per-word scan into an O(L) bucket lookup. The bucket-prune-on-visit is essential — without it the inner loop revisits.

Pinterest-specific tips

Pinterest L5 interviewers want the wildcard bucket explicitly. Don't just say 'BFS' — say 'BFS over implicit graph where edges are one-edit-away, computed via wildcard buckets.' If they ask 'can you go faster?' that's your cue for bidirectional BFS from both ends, which roughly halves the search space. Mention bidirectional even if you don't implement it.

Common mistakes

  • Forgetting that endWord MUST be in wordList — if it's not, return 0 immediately.
  • Not pruning wildcard buckets after visiting — same word reached through multiple paths bloats the queue.
  • Using q.shift() repeatedly on huge queues — use a head pointer.
  • Counting edges instead of nodes — the output is the SEQUENCE LENGTH (number of words), not the number of transformations.

Follow-up questions

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

  • Word Ladder II (LeetCode 126) — return ALL shortest sequences, not just the length.
  • Bidirectional BFS — search from both endpoints, meet in the middle.
  • Variable-cost edges (some transformations cheaper than others) — Dijkstra.
  • Streaming wordList — words arrive online, maintain the shortest path.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Is bidirectional BFS worth the extra code?

At L=10, N=5000 it roughly halves runtime. For interview purposes, mentioning it without implementing is enough unless the interviewer specifically asks 'can you go faster.'

Why is the wildcard trick faster than pairwise?

Pairwise is O(N^2). Wildcards reduce 'find all one-edit-away words' from an O(N) per-word scan to an O(L) bucket lookup. Total cost is O(N * L^2) vs O(N^2 * L).

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →