Marauder Bot

Problem

You are given a start word, an end word, and a list of allowed words. Find the length of the shortest sequence of transformations from start to end, where each step changes exactly one letter and every intermediate word must appear in the allowed list. Return 0 if no such sequence exists.

Example. From hit to cog, with an allowed list containing hot, dot, dog, lot, log, and cog, one shortest sequence is hit → hot → dot → dog → cog, a length of 5.

Key idea

Treat every allowed word, plus the start word, as a node in a graph, with an edge between any two words that differ in exactly one letter position. Finding the shortest transformation sequence is then just finding the shortest path between two nodes in an unweighted graph, and breadth-first search is built for that: because it explores in complete layers, the first time it reaches the end word is guaranteed to be by the fewest possible steps. The remaining challenge is generating a word's neighbors without comparing it against every other word, which is too slow at scale. Instead, for each letter position, try every letter of the alphabet there and check whether the result exists in a hash set built from the allowed list, removing a word the moment it is used so it cannot be revisited.

Solution

function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const words = new Set(wordList);
  if (!words.has(endWord)) {
    return 0;
  }

  const queue: Array<[string, number]> = [[beginWord, 1]];
  words.delete(beginWord);

  while (queue.length > 0) {
    const [word, steps] = queue.shift() as [string, number];
    if (word === endWord) {
      return steps; // BFS explores by layer, so the first arrival is the shortest path
    }

    // try substituting every position with every other letter of the alphabet
    for (let i = 0; i < word.length; i++) {
      for (let code = 97; code <= 122; code++) {
        const letter = String.fromCharCode(code);
        if (letter === word[i]) {
          continue;
        }
        const candidate = word.slice(0, i) + letter + word.slice(i + 1);
        if (words.has(candidate)) {
          words.delete(candidate); // remove now so it cannot be enqueued again later
          queue.push([candidate, steps + 1]);
        }
      }
    }
  }

  return 0;
}

Complexity

Time: O(M² × N). M is the word length, N the allowed-list size; each word tries roughly 26 × M substitutions, each an O(M) set operation.
Space: O(M × N). For the hash set of allowed words and the breadth-first search queue.

Watch out for

If the end word is not present in the allowed list, no valid sequence can reach it.
Use a hash set, not a list, for the allowed words, so membership checks and removals stay fast.
Remove a word from the set as soon as it is enqueued, not when dequeued, or it can be queued multiple times.

Pattern

This is unweighted shortest-path breadth-first search over an implicit graph, where edges are generated on the fly from a transformation rule instead of given directly; the same idea generalizes to any state-transition search space.

Word Ladder