127. Word Ladder

At a Glance

Topic: Hash Table
Pattern: Analyze Pattern
Difficulty: Hard
LeetCode: 127

Problem Statement

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. Note that beginWord does not need to be in wordList.
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.

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","do...

Approach & Solution Steps

Brute force — explore all edit paths with DFS — exponential — wrong for shortest unless bounded.
BFS from start — layer-by-layer shortest path in unweighted graph — O(N * L^2) time (with adjacency-by-pattern trick O(N * L * 26) or bucket BFS) — optimal family.

Optimal JS Solution

function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) {
    return 0;
  }
  const queue = [{ word: beginWord, length: 1 }];
  const visited = new Set([beginWord]);
  while (queue.length > 0) {
    const current = queue.shift();
    if (current.word === endWord) {
      return current.length;
    }
    const chars = current.word.split('');
    for (let index = 0; index < chars.length; index += 1) {
      const original = chars[index];
      for (let code = 'a'.charCodeAt(0); code <= 'z'.charCodeAt(0); code += 1) {
        const letter = String.fromCharCode(code);
        if (letter === original) {
          continue;
        }
        chars[index] = letter;
        const nextWord = chars.join('');
        if (!wordSet.has(nextWord) || visited.has(nextWord)) {
          continue;
        }
        visited.add(nextWord);
        queue.push({ word: nextWord, length: current.length + 1 });
      }
      chars[index] = original;
    }
  }
  return 0;
}

Edge Cases & Pitfalls

Always consider empty or null inputs.
Watch out for off-by-one index errors.