hard

Word Ladder

Find the shortest chain of one-letter word changes that turns a start word into an end word.

1. Define the problem

Word Ladder

Given beginWord, endWord, and a wordList, find the length of the shortest transformation sequence from beginWord to endWord, changing only one letter at a time, where every intermediate word must exist in wordList. Return 0 if no such sequence exists. Treat every word as a node and every one-letter change to another word in the list as an edge . Then breadth-first search from beginWord finds the shortest chain, because it explores one letter-change away before any two letter-changes away.

Constraints

  • 1 ≤ beginWord.length ≤ 10
  • endWord.length == beginWord.length
  • 1 ≤ wordList.length ≤ 5000
  • wordListi.length == beginWord.length
  • beginWord, endWord, and wordListi consist of lowercase English letters
  • beginWord != endWord
  • All the words in wordList are unique

Example

InputbeginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output5

Explanation One shortest transformation is hit -> hot -> dot -> dog -> cog, a sequence of 5 words.

2. Know the words first

In plain terms

Node
One item in the graph being searched — here, a single word.
Edge
A connection between two nodes — here, two words that differ by exactly one letter.
3. Visualize the solution

One cell per word — each shows how long the chain is when BFS first reaches it

One cell per word — each shows how long the chain is when BFS first reaches it
Statusstep 1

Start the queue with hit, sequence length 1. Every other word is still unreached.

What happens in this step

wordSet = {hot, dot, dog, lot, log, cog}
queue = [(hit, len1)]   visited = {hit}

endWord "cog" is in wordSet, so a path is possible.
Step 1 of 5

Steps to visualize

  1. The row has one slot for each of the seven words in play: beginWord "hit" plus the six words in wordList.
  2. A slot shows — until the search reaches that word; then it shows the length of the chain that got there.
  3. If endWord is not in wordList, there is no way to reach it — return 0 immediately.
  4. Start a queue with beginWord, sequence length 1.
  5. Dequeue a word; for every position, try swapping in each other letter of the alphabet.
  6. If the result is in wordList and has not been visited, enqueue it at length + 1.
  7. The first time endWord is dequeued, its length is the shortest sequence.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per word — each shows how long the chain is when BFS first reaches it
Statusstep 1

Start the queue with hit, sequence length 1. Every other word is still unreached.

What happens in this step

wordSet = {hot, dot, dog, lot, log, cog}
queue = [(hit, len1)]   visited = {hit}

endWord "cog" is in wordSet, so a path is possible.
Step 1 of 5
5. Solution

Solution

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

  const alphabet = 'abcdefghijklmnopqrstuvwxyz';
  const queue = [[beginWord, 1]];
  const visited = new Set([beginWord]);

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

    for (let i = 0; i < word.length; i++) {
      for (const ch of alphabet) {
        if (ch === word[i]) continue;
        const candidate = word.slice(0, i) + ch + word.slice(i + 1);
        if (wordSet.has(candidate) && !visited.has(candidate)) {
          visited.add(candidate);
          queue.push([candidate, steps + 1]);
        }
      }
    }
  }

  return 0;
}
Time
O(n * L^2 * 26)
Space
O(n * L)
6. Test cases

Test cases

InputExpectedCovers
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]5example from the docstring
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]0endWord is missing from wordList, so no path can exist
beginWord = "hot", endWord = "dot", wordList = ["dot"]2a one-letter change reaches the target directly
beginWord = "a", endWord = "c", wordList = ["a","b","c"]2a distractor word (b) exists but the direct change is shorter
beginWord = "hot", endWord = "dog", wordList = ["hot","dog"]0the words differ in more than one letter with no intermediate bridge
beginWord = "cat", endWord = "cot", wordList = ["cot","dot","cat"]2multiple candidate words, but only one is a valid one-letter change
beginWord = "hit", endWord = "dot", wordList = ["hot","dot"]3a short chain requiring exactly one intermediate word

Keep reading