Skip to main content

74. Word Ladder

mediumAsked at Vercel

Find the shortest transformation sequence between two words, changing one letter at a time. Vercel asks this for BFS on an implicit graph — same shape as their config-rollout path-finding through compatible intermediate states.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; BFS on implicit graph expected.
  • Blind (2026-Q1)— Listed in Vercel platform engineer screen.

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, 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: hit -> hot -> dot -> dog -> cog.

Example 2

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

Approaches

1. BFS with neighbor generation by pairwise comparison

BFS; at each word, scan all wordList for one-letter-different neighbors.

Time
O(N^2 * L)
Space
O(N * L)
// O(N^2 * L) is slow for N=5000. Use the wildcard-pattern trick.

Tradeoff: Quadratic in N; slow at the upper constraint.

2. BFS with wildcard pattern map (optimal)

Precompute, for each word, all wildcard patterns ('h*t', '*it', 'hi*'). Map pattern -> list of words. BFS uses this for O(L) neighbor expansion per word.

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

Tradeoff: Pattern preprocessing is O(N*L^2). BFS is O(N*L) for the queue + O(L) per neighbor expansion. Bidirectional BFS gives a further constant-factor speedup.

Vercel-specific tips

Vercel grades the wildcard-pattern map trick. Bonus signal: offering bidirectional BFS (search from both ends simultaneously, meet in the middle) as a further optimization. Also flag the endWord-not-in-list early exit.

Common mistakes

  • Generating neighbors by comparing every pair — O(N^2 * L), TLE.
  • Forgetting to mark beginWord as visited — infinite revisit.
  • Not checking endWord in wordList — wastes a full BFS.

Follow-up questions

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

  • Word Ladder II (LC 126, hard) — return all shortest paths.
  • Bidirectional BFS — meet in the middle.
  • Word distance — minimum edits between any two 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 wildcard patterns?

Two words differ by one letter iff they share a wildcard pattern at the differing position. Storing words by pattern lets us find all one-letter-neighbors in O(L) instead of O(N).

Bidirectional BFS — when does it help?

When the average degree is high. Two BFS waves of depth d/2 explore exponentially fewer nodes than one wave of depth d. Cuts runtime roughly by sqrt.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →