Skip to main content

67. Word Ladder

hardAsked at Datadog

Find the shortest transformation sequence from beginWord to endWord, changing one letter at a time, using only words from a dictionary. Datadog uses this as a BFS-on-implicit-graph question — same pattern they use for shortest-path queries on dynamic service topologies.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — graded on BFS + neighbor generation.
  • LeetCode Discuss (2025-08)— Datadog tagged.

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.

Example 2

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

Approaches

1. BFS, generate neighbors by pairwise comparison

For each word in queue, scan all wordList for one-letter neighbors.

Time
O(N^2 * L)
Space
O(N)
// Pairwise O(N) neighbor scan per node = O(N^2 * L) overall. Too slow for N=5000.

Tradeoff: Quadratic in N. Datadog will push for the pattern-bucket approach.

2. BFS with pattern-bucket index (optimal)

Pre-index every word with wildcards: 'hot' -> 'h*t', '*ot', 'ho*'. Each wildcard pattern points to its words. Neighbor lookup is O(L).

Time
O(N * L^2)
Space
O(N * L)
function ladderLength(beginWord, endWord, wordList) {
  const words = new Set(wordList);
  if (!words.has(endWord)) return 0;
  const patterns = new Map();
  for (const w of wordList) {
    for (let i = 0; i < w.length; i++) {
      const p = w.substring(0, i) + '*' + w.substring(i + 1);
      if (!patterns.has(p)) patterns.set(p, []);
      patterns.get(p).push(w);
    }
  }
  const visited = new Set([beginWord]);
  let q = [beginWord];
  let steps = 1;
  while (q.length) {
    const next = [];
    for (const w of q) {
      if (w === endWord) return steps;
      for (let i = 0; i < w.length; i++) {
        const p = w.substring(0, i) + '*' + w.substring(i + 1);
        for (const n of (patterns.get(p) || [])) {
          if (!visited.has(n)) {
            visited.add(n);
            next.push(n);
          }
        }
      }
    }
    q = next;
    steps++;
  }
  return 0;
}

Tradeoff: Pattern-bucket index reduces neighbor lookup to O(L). Total O(N * L^2). Datadog-canonical: same shape as their pre-indexed reverse lookups for shortest-path queries.

Datadog-specific tips

Datadog grades on pre-indexing. Without it, BFS is N^2 per level and won't survive N=5000. The wildcard-pattern bucket is a classic transformation: turn 'neighbor lookup' from O(N*L) per word into O(L) per word.

Common mistakes

  • Generating neighbors by enumerating 25*L letters per word — works but is L^2 * 25 in the inner loop.
  • Forgetting to check if endWord is in wordList — returns wrong answer if not.
  • Counting nodes vs edges — the answer is the number of WORDS, which is edges + 1.

Follow-up questions

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

  • Word Ladder II (LC 126) — return all shortest paths.
  • Bidirectional BFS — halves the search space.
  • Datadog-style: shortest path on a dynamic service topology with pre-indexed buckets.

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 pattern buckets?

Two words are neighbors iff they share a wildcard pattern. Pre-indexing maps pattern -> words, so neighbor lookup is O(L) instead of O(N).

Bidirectional BFS?

Run BFS from both ends; stop when they meet. Reduces complexity from b^d to 2 * b^(d/2). Big speedup for long ladders.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →