Word Ladder

Examples

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5

One shortest chain is hit -> hot -> dot -> dog -> cog, which has 5 words in it.

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0

cog never appears in the word list, so there's no way to end the sequence on it.

Input: beginWord = "a", endWord = "c", wordList = ["a","b","c"]
Output: 3

a -> b -> c: two one-letter changes, three words total.

Constraints

• 1 <= beginWord.length <= 10

• endWord.length == beginWord.length

• All words consist of lowercase English letters and are the same length.

• wordList contains no duplicates, and beginWord != endWord.

Approach

Picture every word as a node, with an edge connecting two words that differ by exactly one letter. The question "what's the shortest chain from beginWord to endWord" is then just "what's the shortest path between two nodes in this graph" - and shortest path in an unweighted graph is exactly what BFS is for.

Start a BFS from beginWord, expanding one "layer" (one letter change) at a time, and stop the moment endWord is reached - the number of steps taken to get there, plus one for the starting word, is the answer. Mark each word as visited the moment it's discovered (not when it's popped) so the same word is never queued twice.

The only real design choice is how you find a word's neighbors:

- Brute force: compare the current word against every remaining word in the list, checking whether they differ in exactly one position. - Optimal: for the current word, try replacing each letter position with every other letter of the alphabet, and look up whether that new word exists in a Set built from wordList - each lookup is O(1), independent of how many words are left in the list.

Solutions

Brute Force - Compare Against Remaining Words

Run a standard BFS, but to find each word's neighbors, scan through every word still left in the dictionary and check whether it differs from the current word in exactly one letter position.

function ladderLength(beginWord, endWord, wordList) {
  const remaining = new Set(wordList);
  if (!remaining.has(endWord)) return 0;

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

  const queue = [[beginWord, 1]];

  while (queue.length > 0) {
    const [word, steps] = queue.shift();
    if (word === endWord) return steps;

    for (const candidate of Array.from(remaining)) {
      if (differsByOne(word, candidate)) {
        remaining.delete(candidate);
        queue.push([candidate, steps + 1]);
      }
    }
  }

  return 0;
}

Time: O(N² × L) - each of N words may be compared against N others, each comparison scanning L letters · Space: O(N × L)

Optimal - BFS with Generated Neighbors

Put the whole word list into a Set for O(1) lookups. For each word popped from the BFS queue, generate every possible one-letter substitution (26 letters × word length candidates) and check each against the Set - any hit is a real neighbor.

function ladderLength(beginWord, endWord, wordList) {
  const remaining = new Set(wordList);
  if (!remaining.has(endWord)) return 0;

  const queue = [[beginWord, 1]];
  const alphabet = "abcdefghijklmnopqrstuvwxyz";

  while (queue.length > 0) {
    const [word, steps] = queue.shift();
    if (word === endWord) return steps;

    for (let i = 0; i < word.length; i++) {
      for (const letter of alphabet) {
        if (letter === word[i]) continue;

        const candidate = word.slice(0, i) + letter + word.slice(i + 1);
        if (remaining.has(candidate)) {
          remaining.delete(candidate); // mark visited so it's never queued twice
          queue.push([candidate, steps + 1]);
        }
      }
    }
  }

  return 0;
}

Time: O(N × L × 26) - for each of N words, try 26 letters at each of L positions · Space: O(N × L)