Skip to main content

127. Word Ladder

hardAsked at Elastic

Find the shortest transformation sequence from one word to another, changing one letter at a time. Elastic uses this BFS-on-a-word-graph problem because edit-distance graph traversal and fuzzy query shortest paths underpin Elasticsearch's fuzziness and Levenshtein automaton query routing.

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

Source citations

Public interview reports confirming this problem appears in Elastic loops.

  • Glassdoor (2025-12)— Elastic senior SWE candidates report BFS on implicit graphs appearing as a hard question in onsite rounds, often framed around edit distance.
  • Blind (2025-10)— Word Ladder cited in Elastic interview threads as a problem connecting graph traversal to fuzzy search — a natural fit for Elastic's domain.

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
  • 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: 'cog' is not in wordList, so no valid transformation sequence exists.

Approaches

1. BFS with wildcard pattern neighbors

BFS from beginWord. For each word, generate all wildcard patterns (e.g., 'h*t', '*it', 'hi*') and pre-group dictionary words by pattern. Finding neighbors = looking up the word's patterns in the pattern map, excluding already-visited words.

Time
O(m² * n) where m = word length, n = word list size
Space
O(m² * n)
function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  // Build pattern -> [words] map
  const patternMap = new Map();
  for (const word of [beginWord, ...wordList]) {
    for (let i = 0; i < word.length; 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 queue = [[beginWord, 1]]; // [word, steps]
  while (queue.length > 0) {
    const [word, steps] = queue.shift();
    for (let i = 0; i < word.length; i++) {
      const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
      for (const neighbor of (patternMap.get(pattern) || [])) {
        if (neighbor === endWord) return steps + 1;
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push([neighbor, steps + 1]);
        }
      }
    }
  }
  return 0;
}

Tradeoff: Pre-building the pattern map avoids O(26 * m) character substitutions per word during BFS. More cache-efficient for large wordLists.

2. BFS with bidirectional search

Run BFS from both beginWord and endWord simultaneously. At each step, expand the smaller frontier. Stop when the two frontiers intersect.

Time
O(m² * n) but often much faster in practice
Space
O(m² * n)
function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  let frontA = new Set([beginWord]);
  let frontB = new Set([endWord]);
  const visited = new Set([beginWord, endWord]);
  let steps = 1;
  while (frontA.size > 0 && frontB.size > 0) {
    if (frontA.size > frontB.size) [frontA, frontB] = [frontB, frontA];
    const next = new Set();
    for (const word of frontA) {
      for (let i = 0; i < word.length; i++) {
        for (let c = 97; c <= 122; c++) {
          const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
          if (frontB.has(newWord)) return steps + 1;
          if (wordSet.has(newWord) && !visited.has(newWord)) {
            next.add(newWord);
            visited.add(newWord);
          }
        }
      }
    }
    frontA = next;
    steps++;
  }
  return 0;
}

Tradeoff: Bidirectional BFS reduces the search space from O(b^d) to O(b^(d/2)) where b = branching factor and d = distance. Significant speedup for large word graphs.

Elastic-specific tips

Elastic interviewers value the bidirectional BFS discussion even if you only implement the single-direction version. State: 'Bidirectional BFS is O(b^(d/2)) vs O(b^d) — the same principle behind Elasticsearch's bidirectional text analysis, where analyzers run both at index time and query time to ensure match symmetry.' The domain connection is what elevates a good answer to a great one at Elastic.

Common mistakes

  • Generating neighbors by substituting all 26 characters without checking the word set — always verify the generated word is in wordSet before enqueuing.
  • Returning 0 when endWord is not in wordList without checking first — do this check before building the pattern map.
  • Not tracking visited words — without visited, the BFS can revisit words and loop infinitely.
  • Returning steps instead of steps + 1 on finding endWord — the sequence length includes the endWord itself.

Follow-up questions

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

  • Word Ladder II (LC 126) — return all shortest transformation sequences (backtracking on BFS level graph).
  • Minimum Genetic Mutation (LC 433) — same problem with a 4-character alphabet.
  • How does Elasticsearch's fuzzy query use a Levenshtein automaton to bound the graph search space?

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 for shortest path?

BFS finds the shortest path by exploring all nodes at distance d before any node at distance d+1. DFS can find a path, but not necessarily the shortest one.

Why pre-build a pattern map instead of substituting all 26 characters?

The pattern map groups dictionary words by their wildcard patterns, so neighbor lookup is O(1) per pattern. Substituting all 26 characters is O(26 * m) per word but generates non-dictionary words that must be filtered — similar overhead with worse cache behavior.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →