Word Ladder

The problem

You are given two words, beginWord and endWord, and a list of allowed words, wordList. All the words have the same length, and beginWord and endWord are different words. A ladder is a sequence of words that starts with beginWord and ends with endWord, in which each word differs from the one before it in exactly one position. Every word after the first must be in wordList; beginWord does not have to be. Return the number of words in the shortest ladder, counting both beginWord and endWord. If there is no ladder, return 0.

What to write

function solve(beginWord: string, endWord: string, wordList: string[]): number

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

Output
5

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

Output
0

Constraints

All words are lowercase and have equal length.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   All the words have the same length and use only lowercase letters, and one move changes one letter. So a word has at most 25 other choices in each position, however long wordList is. And if endWord is not in the list, no ladder can end on it: the answer is 0.

2. Hint 2: Ask a smaller question

   In example 1, which allowed words are exactly one change away from hit? Which new words are one more change away from those? Keep going. After how many changes does cog first show up, and could any ladder have reached it sooner?

3. Hint 3: Name the pattern

   Picture every word as a point, with a link between two words that differ in one letter. A ladder is a route along links, and you want the shortest route when every link costs the same. That is breadth-first search by distance: reach everything one link away first, then two links away, and so on. Read the lesson on breadth-first search by distance.

4. Hint 4: State the invariant

   Reached words wait in a queue and leave in the order they joined. Each carries its ladder length, the number of words from beginWord to it. Words leave the queue shortest first. A word leaves the set of unreached words the moment it joins the queue, so it joins once, with the length of its shortest ladder.

5. Hint 5: Sketch the pseudocode

   Make a set of wordList; without endWord, return 0. Queue beginWord with length 1; drop it from the set. While the queue has words: take the front one. If it is endWord, return its length. Change each position to each letter; any result in the set moves to the queue with length + 1. After the loop, return 0.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Breadth-first search explores word transformations in increasing sequence length. Remove words from the unvisited set as soon as they are enqueued.

The slow way

Follow every possible chain: from beginWord, step to any allowed word one letter away that the chain has not used, and remember the shortest chain that reaches endWord. It is correct, but the same words are reached again and again through different chains. With only the 16 four-letter words made of a and b, going from aaaa to bbbb builds about 25,000 chains.

The insight

Treat each word as a point and each allowed one-letter change as a link. Reach the words in rings: first everything one change from beginWord, then two changes, then three. The first time you meet a word is then by a shortest ladder, so each word is handled once. This ring-by-ring order is breadth-first search, and a queue produces it.

Step by step

1. Put wordList in a set; if endWord is missing, there is no ladder. A set answers "is this word allowed and not reached yet?" in about one step. Every word after the first must come from the list, the last one too, so without endWord in it the answer is 0.
2. Start a queue with beginWord at length 1 and take it out of the set. The length kept with a word is the number of words in its ladder, and beginWord alone is a ladder of 1. beginWord is already reached, so it must not stay among the unreached words.
3. Take the word at the front of the queue, with its ladder length. A queue is a line: words join at the back and leave from the front. So words leave in the order they were reached, which is the order of ladder length, shortest first.
4. If it is endWord, its ladder length is the answer. Words leave the queue shortest first, so no ladder to endWord can be shorter than the one that brought it to the front.
5. Try each of the 26 letters in each position of the word. This builds 26 strings for each position: the 25 that differ there, and the word itself, which is harmless because it has already left the set. No pass over wordList is needed, however long the list is.
6. A result still in the set leaves the set and joins the queue. Being in the set means the word is allowed and has not been reached before. So its shortest ladder is the taken word's ladder plus one word. Removing it at once keeps other words from queuing it again.
7. The queue ran out before endWord was reached: there is no ladder. Every word that can be reached from beginWord has been through the queue. If endWord was not one of them, no chain of allowed changes leads to it, and the answer is 0.

The same numbered steps are the comments in each solution.

function solve(beginWord, endWord, wordList) {
  // 1. Put wordList in a set; if endWord is missing, there is no ladder
  // As the search goes on, this set holds the words not reached yet.
  const words = new Set(wordList);
  if (!words.has(endWord)) return 0;
  // 2. Start a queue with beginWord at length 1 and take it out of the set
  // Each queue entry is a pair: a word and the length of its ladder.
  const q = [[beginWord, 1]];
  words.delete(beginWord);
  // 3. Take the word at the front of the queue, with its ladder length
  // Removing the first item of an array is slow, so nothing is removed:
  // h is the position of the front, and q.length grows as words join.
  for (let h = 0; h < q.length; h++) {
    const [word, d] = q[h];
    // 4. If it is endWord, its ladder length is the answer
    if (word === endWord) return d;
    // 5. Try each of the 26 letters in each position of the word
    for (let i = 0; i < word.length; i++)
      // Character codes 97 to 122 are the letters a to z.
      for (let c = 97; c <= 122; c++) {
        const next =
          word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
        // 6. A result still in the set leaves the set and joins the queue
        // delete returns true only if the word was in the set.
        if (words.delete(next)) q.push([next, d + 1]);
      }
  }
  // 7. The queue ran out before endWord was reached: there is no ladder
  return 0;
}

function solve(beginWord: string, endWord: string, wordList: string[]): number {
  // 1. Put wordList in a set; if endWord is missing, there is no ladder
  // As the search goes on, this set holds the words not reached yet.
  const words = new Set(wordList);
  if (!words.has(endWord)) return 0;
  // 2. Start a queue with beginWord at length 1 and take it out of the set
  // Each queue entry is a pair: a word and the length of its ladder.
  const q: [string, number][] = [[beginWord, 1]];
  words.delete(beginWord);
  // 3. Take the word at the front of the queue, with its ladder length
  // Removing the first item of an array is slow, so nothing is removed:
  // h is the position of the front, and q.length grows as words join.
  for (let h = 0; h < q.length; h++) {
    const [word, d] = q[h];
    // 4. If it is endWord, its ladder length is the answer
    if (word === endWord) return d;
    // 5. Try each of the 26 letters in each position of the word
    for (let i = 0; i < word.length; i++)
      // Character codes 97 to 122 are the letters a to z.
      for (let c = 97; c <= 122; c++) {
        const next =
          word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
        // 6. A result still in the set leaves the set and joins the queue
        // delete returns true only if the word was in the set.
        if (words.delete(next)) q.push([next, d + 1]);
      }
  }
  // 7. The queue ran out before endWord was reached: there is no ladder
  return 0;
}

import string
from collections import deque


def solve(beginWord, endWord, wordList):
    # 1. Put wordList in a set; if endWord is missing, there is no ladder
    # As the search goes on, this set holds the words not reached yet.
    words = set(wordList)
    if endWord not in words:
        return 0
    # 2. Start a queue with beginWord at length 1 and take it out of the set
    # Each queue entry is a pair: a word and the length of its ladder.
    # A deque is a list that is fast at both ends: append adds at the back,
    # popleft takes from the front. discard does nothing if the word is absent.
    queue = deque([(beginWord, 1)])
    words.discard(beginWord)
    # 3. Take the word at the front of the queue, with its ladder length
    while queue:
        word, length = queue.popleft()
        # 4. If it is endWord, its ladder length is the answer
        if word == endWord:
            return length
        # 5. Try each of the 26 letters in each position of the word
        for i in range(len(word)):
            for letter in string.ascii_lowercase:
                candidate = word[:i] + letter + word[i + 1 :]
                # 6. A result still in the set leaves the set and joins the queue
                if candidate in words:
                    words.remove(candidate)
                    queue.append((candidate, length + 1))
    # 7. The queue ran out before endWord was reached: there is no ladder
    return 0

Example 1, traced

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

Output
5

Why it works

The queue hands out words in the order they were reached, so all words with ladder length 2 leave before any with length 3, and so on. A word is queued the first time any ladder reaches it, which is therefore a shortest one. So when endWord comes to the front, its length is the smallest possible.

Time and space

Time O(26 · N · L²), extra space O(N · L). Each of the N words in wordList leaves the queue at most once and tries 26 letters in each of its L positions. Building one changed word takes about L steps, which gives 26 · N · L². The set and queue hold up to N words of L letters.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• The answer counts words, not changes. beginWord starts at length 1, not 0: example 1 takes 4 changes but its ladder has 5 words, and a count that starts at 0 returns 4.
• Take the oldest word in the queue, not the newest. The newest follows one chain deep and can meet endWord on a longer ladder: from bb to ac with the list aa, ab, ac, ba it answers 4, not 3.
• Matching endWord is not enough: the word must be in wordList too. In example 2 cog is one letter from dog but not in the list. A version that returns on the bare match answers 5 instead of 0.

Pattern

Breadth-first search by distance. Builds on Rotting Oranges and Graph Valid Tree.

Keep going