Word Ladder

You are given a start word beginWord, a target word endWord and a dictionary wordList. All words have the same length and use lowercase English letters.

A ladder is a sequence of words that starts with beginWord and ends with endWord, where each word differs from the one before it in exactly one position, and every word after beginWord appears in wordList. beginWord itself does not need to be in the list.

Return the number of words in the shortest ladder, counting both ends. If no ladder exists, return 0.

Example 1

Input: beginWord = "cold", endWord = "warm", wordList = ["cord","card","ward","warm","wold","word","worm"] Output: 5 Why: One shortest ladder is cold → cord → word → worm → warm, which has 5 words. (cold → cord → card → ward → warm is another.)

Example 2

Input: beginWord = "lead", endWord = "gold", wordList = ["load","goad","gold","lend"] Output: 4 Why: lead → load → goad → gold uses 4 words. "lend" is a dead end.

Example 3

Input: beginWord = "cat", endWord = "dog", wordList = ["cot","cog","dot"] Output: 0 Why: "dog" is not in the dictionary, so no ladder can end there.

Constraints

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length, and every word in wordList has that length too
  • 1 <= wordList.length <= 5000
  • All words consist of lowercase English letters; the words in wordList are distinct.
  • beginWord != endWord

Pattern Path · Graphs: Traversal · problem 137 of 169

Model the words as a graph: which pairs of words should be connected by an edge?
You want the fewest steps in a graph whose edges all cost the same. Which traversal finds that directly?
Comparing every pair of words is slow. To find the neighbours of a word, change one letter at a time to each of a..z and look the result up in a set.
Target: O(n · L² · 26) (n · 26 · L candidates, each built in O(L)) time, O(n · L) extra space.

Start simple

Build the full graph by comparing every pair of words letter by letter, then run BFS: O(n² · L) time just to build the edges.

The key idea

Treat every word as a node of a graph and connect two words when they differ in exactly one letter. Each step of a ladder is one edge, so the shortest ladder is a shortest path in an unweighted graph, which is exactly what breadth-first search finds: BFS visits words in order of their distance from beginWord, so the first time it reaches endWord the distance is minimal.

You never need to build the graph up front. For the current word, try every position and every letter a..z; each candidate that is in the dictionary set and not yet visited is a neighbour. That is 26 · L set lookups per word instead of comparing it against all n words.

Mark a word visited when you enqueue it, not when you dequeue it, so it is never queued twice. If endWord is not in the dictionary, answer 0 immediately. Each word is processed at most once, and building each candidate string costs O(L).

Complexity

  • Time: O(n · L² · 26) (n · 26 · L candidates, each built in O(L))
  • Space: O(n · L)

Python

import string
from collections import deque


class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        words = set(wordList)
        if endWord not in words:
            return 0
        queue = deque([(beginWord, 1)])   # (word, ladder length so far)
        visited = {beginWord}
        while queue:
            word, length = queue.popleft()
            if word == endWord:
                return length
            # Every dictionary word that differs from `word` in one position.
            for i in range(len(word)):
                for ch in string.ascii_lowercase:
                    candidate = word[:i] + ch + word[i + 1:]
                    if candidate in words and candidate not in visited:
                        visited.add(candidate)
                        queue.append((candidate, length + 1))
        return 0

JavaScript

var ladderLength = function(beginWord, endWord, wordList) {
  const words = new Set(wordList);
  if (!words.has(endWord)) return 0;
  const letters = "abcdefghijklmnopqrstuvwxyz";
  const queue = [[beginWord, 1]];   // [word, ladder length so far]
  const visited = new Set([beginWord]);
  for (let head = 0; head < queue.length; head++) {
    const [word, length] = queue[head];
    if (word === endWord) return length;
    // Every dictionary word that differs from `word` in one position.
    for (let i = 0; i < word.length; i++) {
      for (const ch of letters) {
        const candidate = word.slice(0, i) + ch + word.slice(i + 1);
        if (words.has(candidate) && !visited.has(candidate)) {
          visited.add(candidate);
          queue.push([candidate, length + 1]);
        }
      }
    }
  }
  return 0;
};

What the interviewer is checking

The interviewer wants you to recognise an implicit graph, choose BFS for an unweighted shortest path, and generate neighbours cleverly instead of comparing all pairs.

Mistakes to avoid

  • Forgetting to return 0 when endWord is missing from the dictionary.
  • Counting steps (edges) instead of words; the answer includes both ends.
  • Marking words visited only when dequeued, which can queue the same word many times.
  • Using DFS, which finds a ladder but not necessarily the shortest.

Follow-ups to expect

  • Return all shortest ladders, not just the length. (BFS layers plus parent links, then backtrack.)
  • How can you speed up the search? (Bidirectional BFS from both ends.)
  • What if letters can also be inserted or deleted? (Edit-distance-1 neighbours via wildcard patterns.)

In real software

Spell checkers and fuzzy search generate one-edit neighbours of a word the same way, and network tools use BFS to find the minimum number of hops between two machines.

Practice next

Next Post Previous Post
No Comment
Add Comment
comment url