Skip to main content

127. Word Ladder

hardAsked at Linear

Find the shortest transformation sequence from beginWord to endWord, changing one letter at a time, using only dictionary words. Linear asks this to test whether you model it as BFS on an implicit graph — and whether you know the wildcard-key optimization to build adjacency lists efficiently.

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

Source citations

Public interview reports confirming this problem appears in Linear loops.

  • Glassdoor (2025-11)— Cited in Linear SWE onsite reports as a hard BFS problem for senior engineering roles.
  • Blind (2025-10)— Mentioned in Linear interview threads as a challenging graph-modeling problem.

Problem

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence beginWord -> s1 -> s2 -> ... -> sk such that: every adjacent pair 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.
  • beginWord != endWord
  • All the words in wordList are unique.

Examples

Example 1

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

Explanation: hit -> hot -> dot -> dog -> cog (5 words).

Example 2

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

Explanation: endWord 'cog' is not in the word list.

Approaches

1. BFS with pairwise neighbor check

BFS from beginWord; for each word in the queue, check all dictionary words that differ by exactly one character.

Time
O(n^2 * L)
Space
O(n)
function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  function oneDiff(a, b) {
    let diffs = 0;
    for (let i = 0; i < a.length; i++) if (a[i] !== b[i]) diffs++;
    return diffs === 1;
  }
  const q = [[beginWord, 1]];
  const visited = new Set([beginWord]);
  while (q.length) {
    const [word, depth] = q.shift();
    for (const next of wordSet) {
      if (!visited.has(next) && oneDiff(word, next)) {
        if (next === endWord) return depth + 1;
        visited.add(next);
        q.push([next, depth + 1]);
      }
    }
  }
  return 0;
}

Tradeoff: O(n^2 * L) — for each word in the queue, scan all n dictionary words and compare L characters. Correct but slow for large dictionaries.

2. BFS with wildcard adjacency map (optimal)

Precompute a map from wildcard patterns (e.g. 'h*t') to all words matching that pattern. Neighbors of a word are all words sharing any wildcard pattern.

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

Tradeoff: O(n * L^2) preprocessing for the pattern map, O(n * L) BFS traversal. The wildcard pattern groups all one-edit neighbors — each BFS step expands in O(L * avg_neighbors) instead of O(n * L).

Linear-specific tips

Frame this as a graph problem before coding: 'Words are nodes; edges connect words that differ by one character. I want the shortest path from beginWord to endWord — classic BFS.' Then explain the wildcard optimization: 'Instead of checking all n words per step, I precompute patterns like h*t and group words by pattern — neighbors are all words sharing a pattern.' This two-step reasoning is exactly what Linear expects for a hard problem.

Common mistakes

  • Modeling as DFS instead of BFS — DFS finds a path but not necessarily the shortest one.
  • Not checking if endWord is in the word list — if it's absent, return 0 immediately.
  • Not marking words as visited when they're added to the queue (only when popped) — leads to re-processing and incorrect results or TLE.

Follow-up questions

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

  • Word Ladder II (LC 126) — return all shortest transformation sequences, not just the length.
  • How does bidirectional BFS improve the runtime? (It reduces the search space from O(b^d) to O(2 * b^{d/2}).)
  • What if character substitutions have different costs (weighted 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

Why BFS and not DFS?

BFS explores all paths of length 1, then length 2, etc. The first time it reaches endWord, it has found the shortest path. DFS doesn't guarantee shortest.

What is the wildcard pattern trick?

For word 'hit', patterns are '*it', 'h*t', 'hi*'. All words sharing a pattern differ from 'hit' by exactly one character. Precomputing this map makes neighbor lookup O(L) per word instead of O(n*L).

Should I mark visited when enqueueing or dequeuing?

Mark when enqueueing. If you wait until dequeuing, the same word gets added to the queue multiple times, causing redundant processing and inflating the depth count.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →