Skip to main content

87. Word Ladder

hardAsked at Reddit

Find the shortest transformation sequence from beginWord to endWord (one-letter change per step). Reddit uses this BFS problem to test graph exploration — the same shortest-path shape used when tracing comment-edit chains across moderator interventions.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit on-site graph hard.

Problem

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words such that: every adjacent pair of words differs by a single letter; every word in the sequence is in wordList. Note that beginWord does not need to be in 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.

Example 2

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

Approaches

1. BFS with naive neighbor check

BFS; for each word, scan dictionary to find one-letter-different words.

Time
O(N^2 * L)
Space
O(N)
// Anti-pattern: O(N^2) pair comparisons.

Tradeoff: TLE for n=5000.

2. BFS with wildcard buckets (optimal)

Preprocess: for each word, generate L wildcard patterns (h*t, *ot, ho*) -> list of matching words. BFS using these buckets.

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

Tradeoff: The wildcard bucket dramatically reduces neighbor lookup time. The classic optimization.

Reddit-specific tips

Reddit interviewers want the wildcard-bucket trick. Bonus signal: discuss bidirectional BFS as a further speedup (search from both ends, meet in the middle).

Common mistakes

  • Including beginWord in the wordList check (it doesn't need to be there).
  • Forgetting to return 0 when endWord is not reachable.
  • Off-by-one on depth (the answer counts words, including beginWord).

Follow-up questions

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

  • Word Ladder II (LC 126) — return all shortest sequences.
  • Bidirectional BFS implementation.
  • Snakes and Ladders (LC 909) — similar BFS.

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 wildcards instead of direct comparison?

Naive neighbor finding is O(N) per word. Wildcards turn it into O(L) bucket lookups.

Bidirectional BFS speedup?

Two halves with depth D/2 each instead of one with depth D — exponentially faster.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →