Skip to main content

69. Word Ladder

hardAsked at Workday

Find the shortest transformation sequence from beginWord to endWord changing one letter at a time, where each intermediate is in wordList. Workday uses this for BFS-on-graph reasoning — same shape as finding the shortest role-transition chain through approved promotion paths.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE3 onsite.

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 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
  • 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 neighbor enumeration

For each word at each level, try every single-letter substitution and check if it's in the dict.

Time
O(N * L * 26) per level
Space
O(N)
// BFS, swap each char of each word to a-z, check if in dict

Tradeoff: Simple but each neighbor check is L * 26 work.

2. BFS with pattern-bucket adjacency

Precompute pattern buckets: for each word, generate 'h*t', '*it', 'hi*' as keys mapping to word lists. BFS by visiting all words in the same pattern bucket.

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

Tradeoff: Pattern buckets convert neighbor enumeration to O(L) lookups. Trades preprocessing for runtime.

Workday-specific tips

Workday wants BFS and the pattern-bucket optimization. Brute-force neighbor enumeration is O(L * 26) per word — pattern buckets reduce to O(L) per word, big at scale. Mention bidirectional BFS as an even sharper variant.

Common mistakes

  • Using DFS — won't find shortest path.
  • Adding visited too late — same word enqueued multiple times.
  • Forgetting to short-circuit if endWord not in wordList.

Follow-up questions

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

  • Word Ladder II (LC 126) — return all shortest sequences.
  • Bidirectional BFS from both ends.
  • What if word lengths vary?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

BFS over DFS?

BFS finds shortest path in unweighted graphs. DFS would find any path — but not the shortest.

Bidirectional BFS?

Start BFS from both ends; meet in the middle. Reduces time complexity dramatically at the cost of more code.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →