Skip to main content

127. Word Ladder

hardAsked at eBay

eBay's catalog team maps product category transitions — how many steps does it take to reclassify a listing from one category to a related one, changing only one attribute at a time? Word Ladder is a BFS shortest-path problem on an implicit graph that eBay uses to test graph construction, BFS level-tracking, and neighbor-generation efficiency.

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

Source citations

Public interview reports confirming this problem appears in eBay loops.

  • Glassdoor (2025-11)— Reported in eBay senior SWE onsite discussions as an implicit graph BFS problem.
  • Blind (2025-08)— eBay SWE threads list Word Ladder as an occasional hard problem testing BFS on an implicitly defined graph.

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 of words differs by a single letter, and every si for 1 <= i <= k is in wordList. 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 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 (length 5). Each step changes exactly one letter to a word in the dictionary.

Example 2

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

Explanation: endWord 'cog' is not in wordList, so no transformation sequence exists.

Approaches

1. BFS with wildcard pattern grouping

Build a graph where each word maps to its wildcard patterns (e.g., 'hot' → ['*ot', 'h*t', 'ho*']). Group words by pattern. BFS from beginWord, using patterns to find neighbors. Track visited words to avoid cycles.

Time
O(M² * N) where M is word length and N is dictionary 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]];
  while (queue.length > 0) {
    const [word, level] = 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 level + 1;
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push([neighbor, level + 1]);
        }
      }
    }
  }
  return 0;
}

Tradeoff: O(M² * N) — the pattern map avoids generating all 26 substitutions per position and checking each against the dictionary. This is faster in practice when the dictionary is large. eBay interviewers appreciate the pattern-grouping insight.

2. BFS with 26-character substitution

For each word in the BFS queue, try replacing each character with all 26 letters. If the resulting word is in the dictionary Set and not visited, enqueue it.

Time
O(M * 26 * N)
Space
O(N)
function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  const queue = [[beginWord, 1]];
  const visited = new Set([beginWord]);
  while (queue.length > 0) {
    const [word, level] = queue.shift();
    for (let i = 0; i < word.length; i++) {
      for (let c = 97; c <= 122; c++) { // 'a' to 'z'
        const next = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
        if (next === endWord) return level + 1;
        if (wordSet.has(next) && !visited.has(next)) {
          visited.add(next);
          queue.push([next, level + 1]);
        }
      }
    }
  }
  return 0;
}

Tradeoff: O(26 * M * N) — simpler to implement than the pattern map. For M up to 10 and N up to 5000, this is very fast in practice. The pattern-map approach is theoretically better when N is very large and M is longer.

eBay-specific tips

eBay interviewers want you to first articulate the graph model: 'Each word is a node. Two words are neighbors if they differ by exactly one letter. I need the shortest path from beginWord to endWord — that's BFS.' Then discuss neighbor generation: '26 * M substitutions vs. pattern grouping.' The early return when next === endWord before checking visited is a useful optimization — check for the target before enqueuing. Bidirectional BFS can halve the search space but is complex to code under time pressure; mention it as a theoretical optimization.

Common mistakes

  • Not checking if endWord is in wordList before starting BFS — if it's absent, the answer is always 0.
  • Not marking words as visited when enqueuing (only when dequeuing) — leads to exponential re-processing.
  • Including beginWord in wordList checks — beginWord may or may not be in wordList; handle it by initializing the queue with it regardless.
  • Returning level instead of level + 1 when the endWord is found — the sequence count includes both beginWord and endWord.

Follow-up questions

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

  • Word Ladder II (LC 126) — return all shortest transformation sequences, not just the length; requires tracking paths during BFS.
  • How would bidirectional BFS improve performance? What is the complexity reduction?
  • How would you solve this for a very large dictionary (millions of words) that doesn't fit in memory?

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 this problem?

BFS finds the shortest path in an unweighted graph. DFS would find a path but not necessarily the shortest one without exhaustive search.

What is bidirectional BFS and when does it help?

Run BFS from both beginWord and endWord simultaneously. When the two frontiers meet, the path is found. For a branching factor b and diameter d, standard BFS is O(b^d) while bidirectional is O(b^(d/2) + b^(d/2)) = O(b^(d/2)) — a quadratic speedup.

Why check if next === endWord before checking wordSet.has(next)?

endWord must be in wordList to have a valid path (already checked at the start), so this is equivalent. But checking endWord first allows early exit before the Set lookup — a minor optimization that's worth mentioning.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →