127. Word Ladder

hardAsked at Uber

Given beginWord, endWord, and a word list, find the length of the shortest transformation sequence where each step changes one letter and lands in the list. Uber asks this to test BFS-on-implicit-graphs plus the wildcard-bucket optimization.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Uber loops.

Glassdoor (2026-Q1)— Uber L5 onsite reports include this as a recurring graph hard.
Blind (2025-11)— Mentioned in Uber backend-platform onsite reports.

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 differs by a single letter and every word (except possibly beginWord) is in wordList. Return the number of words in the shortest sequence, 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
All words consist of lowercase English letters.
All the words in wordList are unique.

Examples

Example 1

Input

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

Output

Explanation: hit -> hot -> dot -> dog -> cog has length 5.

Example 2

Input

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

Output

Explanation: endWord not in list.

Approaches

1. Naive BFS — compare every pair

BFS from beginWord. For each frontier word, scan the entire word list and enqueue any word that differs by one letter.

Time: O(N^2 * L)
Space: O(N * L)

function ladderLengthNaive(beginWord, endWord, wordList) {
  const dict = new Set(wordList);
  if (!dict.has(endWord)) return 0;
  function differsByOne(a, b) {
    let d = 0;
    for (let i = 0; i < a.length; i++) if (a[i] !== b[i]) d++;
    return d === 1;
  }
  const visited = new Set([beginWord]);
  let queue = [beginWord], steps = 1;
  while (queue.length) {
    const next = [];
    for (const word of queue) {
      if (word === endWord) return steps;
      for (const w of dict) {
        if (!visited.has(w) && differsByOne(word, w)) {
          visited.add(w);
          next.push(w);
        }
      }
    }
    queue = next;
    steps++;
  }
  return 0;
}

Tradeoff: Conceptually clean but the inner pairwise check is N*L per frontier word. Times out on the 5000-word constraint. Always mention before pivoting.

2. BFS with wildcard buckets (optimal)

Preprocess every word into L wildcard patterns ('h*t', '*ot', 'ho*'). Two words are neighbors iff they share a pattern. BFS uses the bucket map.

Time: O(N * L^2)
Space: O(N * L^2)

function ladderLength(beginWord, endWord, wordList) {
  const dict = new Set(wordList);
  if (!dict.has(endWord)) return 0;
  const L = beginWord.length;
  const buckets = new Map();
  for (const w of wordList) {
    for (let i = 0; i < L; i++) {
      const key = w.slice(0, i) + '*' + w.slice(i + 1);
      if (!buckets.has(key)) buckets.set(key, []);
      buckets.get(key).push(w);
    }
  }
  const visited = new Set([beginWord]);
  let queue = [beginWord], steps = 1;
  while (queue.length) {
    const next = [];
    for (const word of queue) {
      if (word === endWord) return steps;
      for (let i = 0; i < L; 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);
            next.push(neighbor);
          }
        }
      }
    }
    queue = next;
    steps++;
  }
  return 0;
}

Tradeoff: Builds an implicit adjacency graph in O(N * L^2) preprocessing, then BFS is fast. Works within the 5000-word constraint.

3. Bidirectional BFS (further speedup)

BFS simultaneously from both ends, always expanding the smaller frontier. Stop when frontiers meet.

Time: O(N * L^2) but typically faster constants
Space: O(N * L^2)

function ladderLengthBi(beginWord, endWord, wordList) {
  const dict = new Set(wordList);
  if (!dict.has(endWord)) return 0;
  const L = beginWord.length;
  let front = new Set([beginWord]);
  let back = new Set([endWord]);
  const visited = new Set([beginWord, endWord]);
  let steps = 1;
  while (front.size && back.size) {
    if (front.size > back.size) [front, back] = [back, front];
    const next = new Set();
    for (const word of front) {
      for (let i = 0; i < L; i++) {
        for (let c = 97; c <= 122; c++) {
          const cand = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
          if (back.has(cand)) return steps + 1;
          if (dict.has(cand) && !visited.has(cand)) {
            visited.add(cand);
            next.add(cand);
          }
        }
      }
    }
    front = next;
    steps++;
  }
  return 0;
}

Tradeoff: Halves the effective search radius in practice. Especially valuable when N and L are large; same big-O but typically 2-5x faster on real inputs.

Uber-specific tips

Uber interviewers care that you reach for the wildcard-bucket trick once you've named the naive-BFS time bound. Say it out loud: 'Comparing every pair is N^2 per level, that's too much. I'll preprocess each word into L wildcard patterns so neighbors share a bucket.' If you go straight to bidirectional BFS, mention the wildcard buckets as the building block.

Common mistakes

Forgetting to check that endWord is in the dictionary before starting BFS.
Using DFS instead of BFS — DFS doesn't give the shortest path.
Marking the bucket consumed across queries when the same dict is reused — buckets should not be cleared if multiple queries share the dict.

Follow-up questions

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

Word Ladder II (LC 126) — return all shortest sequences, not just the length.
Open the Lock (LC 752) — same BFS pattern with 4-digit wheels.
What if the dictionary is enormous and queries are frequent? (Precompute buckets once.)

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, not DFS or Dijkstra?

Edge weights are all 1, so BFS gives the shortest path in O(V + E). Dijkstra works but adds a log factor with no benefit. DFS doesn't guarantee shortest at all.

Why wildcard buckets over building an explicit adjacency list?

Same idea, different bookkeeping. Buckets are usually less code and use one map instead of N adjacency lists. Asymptotically identical.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →