Skip to main content

23. Word Ladder

hardAsked at Roblox

Find the shortest transformation sequence between two words, changing one letter at a time — Roblox draws on this BFS-on-implicit-graph pattern when computing minimum edit-distance hops in their natural-language chat moderation and avatar-name suggestion systems.

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

Problem

Given a beginWord, an endWord, and a wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, where each transformed word must be in the wordList and differ from the previous word by exactly one letter. Return 0 if no such sequence exists.

Constraints

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • All words have the same length and consist of lowercase English letters
  • beginWord != endWord

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

Explanation: endWord 'cog' not in wordList.

Approaches

1. Brute force — BFS with full neighbor scan

BFS layer by layer. For each word in the queue, compare it to every word in the wordList to find single-letter neighbors. O(N^2 * L) per level.

Time
O(N^2 * L) where N = wordList size, L = word length
Space
O(N)
function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;

  function isNeighbor(a, b) {
    let diff = 0;
    for (let i = 0; i < a.length; i++) if (a[i] !== b[i]) diff++;
    return diff === 1;
  }

  const queue = [[beginWord, 1]];
  const visited = new Set([beginWord]);

  while (queue.length) {
    const [word, steps] = queue.shift();
    for (const next of wordSet) {
      if (!visited.has(next) && isNeighbor(word, next)) {
        if (next === endWord) return steps + 1;
        visited.add(next);
        queue.push([next, steps + 1]);
      }
    }
  }
  return 0;
}

Tradeoff:

2. Optimal — BFS with wildcard pattern indexing

Pre-build a map from wildcard patterns (h*t, *it, hi*) to matching words. During BFS, generate all L patterns for the current word and look up neighbors in O(L) per word instead of O(N*L). Bidirectional BFS halves the search space further.

Time
O(N * L^2)
Space
O(N * L^2)
function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;

  const L = beginWord.length;
  const patternMap = new Map();

  for (const word of [beginWord, ...wordList]) {
    for (let i = 0; i < L; i++) {
      const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
      if (!patternMap.has(pattern)) patternMap.set(pattern, []);
      patternMap.get(pattern).push(word);
    }
  }

  const queue = [[beginWord, 1]];
  const visited = new Set([beginWord]);

  while (queue.length) {
    const [word, steps] = queue.shift();
    for (let i = 0; i < L; i++) {
      const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
      for (const next of (patternMap.get(pattern) || [])) {
        if (next === endWord) return steps + 1;
        if (!visited.has(next)) {
          visited.add(next);
          queue.push([next, steps + 1]);
        }
      }
    }
  }
  return 0;
}

Tradeoff:

Roblox-specific tips

Roblox rates this problem highly for systems roles because the wildcard-pattern trick maps directly to how you'd build an efficient fuzzy-match index — something Roblox needs for chat filter bypass detection (users substituting letters to evade exact-match rules). Be ready to extend: if asked for all shortest paths, shift to BFS level-tracking with a parent map. If asked about large vocabularies, discuss bidirectional BFS cutting the fan-out factor roughly in half.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →