Word ladder

Hard TimeO(n·k·26) SpaceO(n)

Given a start word begin, a target end and a dictionary of words, return how many words are in the shortest chain from begin to end where each step changes exactly one letter and every word after the first is in the dictionary. Return 0 when no such chain exists. All the words are the same length, and the count includes both ends.

Examples

Example 1

Input
begin = "hit"end = "cog"words = ["hot", "dot", "dog", "lot", "log", "cog"]
Output
5
hit → hot → dot → dog → cog is five words, each one letter from the one before it.

Example 2

Input
begin = "hit"end = "cog"words = ["hot", "dot", "dog", "lot", "log"]
Output
0
"cog" is not in the dictionary, so no chain can end on it.

The Code

function ladderLength(begin, end, words) {
  const dictionary = new Set(words);
  if (!dictionary.has(end)) return 0;
  const alphabet = "abcdefghijklmnopqrstuvwxyz";
  const visited = new Set([begin]);
  let frontier = [begin];
  let level = 1;
  while (frontier.length > 0) {
    const next = [];
    for (let i = 0; i < frontier.length; i++) {
      const word = frontier[i];
      if (word === end) return level;
      for (let pos = 0; pos < word.length; pos++) {
        for (let a = 0; a < alphabet.length; a++) {
          const candidate = word.slice(0, pos) + alphabet[a] + word.slice(pos + 1);
          if (dictionary.has(candidate) && !visited.has(candidate)) {
            visited.add(candidate);
            next.push(candidate);
          }
        }
      }
    }
    frontier = next;
    level++;
  }
  return 0;
}
ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]);
Done

The first 16 calls, of 529. This one does not fit on a page.

Step through ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]) call by call

More like this

All strings examples (13) →