Word Ladder

Problem Description

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence where:

• Every adjacent pair of words differs by a single letter.
• Every word in the sequence is in wordList.
• beginWord does not need to be in wordList.

Given beginWord, endWord, and wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Examples

Constraints

• 1 ≤ beginWord.length ≤ 10
• endWord.length == beginWord.length
• 1 ≤ wordList.length ≤ 5000
• wordList[i].length == beginWord.length

BFS Finds Shortest Transformation

This is shortest path on an implicit graph: nodes are words, edges connect words that differ by exactly one letter. BFS finds the minimum number of steps.

The naive approach generates all neighbors by checking every word in the dictionary: O(wordList.length * wordLength). The smarter approach generates all possible one-letter substitutions and checks if each exists in the dictionary: O(wordLength * 26) per word. For wordLength = 10 and wordList.length = 5000, the smart approach is about 5000x faster.

Solution: BFS with Pattern Matching

import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) return 0;

        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        int steps = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            steps++;
            for (int i = 0; i < size; i++) {
                char[] word = queue.poll().toCharArray();
                for (int j = 0; j < word.length; j++) {
                    char orig = word[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == orig) continue;
                        word[j] = c;
                        String next = new String(word);
                        if (next.equals(endWord)) return steps;
                        if (wordSet.contains(next) && !visited.contains(next)) {
                            visited.add(next);
                            queue.offer(next);
                        }
                        word[j] = orig; // restore
                    }
                }
            }
        }
        return 0;
    }
}

from collections import deque

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
        word_set = set(wordList)
        if endWord not in word_set:
            return 0

        queue = deque([beginWord])
        visited = {beginWord}
        steps = 1

        while queue:
            steps += 1
            for _ in range(len(queue)):
                word = queue.popleft()
                for i in range(len(word)):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        if c == word[i]:
                            continue
                        next_word = word[:i] + c + word[i+1:]
                        if next_word == endWord:
                            return steps
                        if next_word in word_set and next_word not in visited:
                            visited.add(next_word)
                            queue.append(next_word)

        return 0

#include <string>
#include <queue>
#include <unordered_set>
#include <vector>

class Solution {
public:
    int ladderLength(std::string beginWord, std::string endWord, std::vector<std::string>& wordList) {
        std::unordered_set<std::string> wordSet(wordList.begin(), wordList.end());
        if (!wordSet.count(endWord)) return 0;

        std::queue<std::string> q;
        std::unordered_set<std::string> visited;
        q.push(beginWord);
        visited.insert(beginWord);
        int steps = 1;

        while (!q.empty()) {
            steps++;
            int sz = q.size();
            while (sz--) {
                std::string word = q.front(); q.pop();
                for (int j = 0; j < (int)word.size(); j++) {
                    char orig = word[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == orig) continue;
                        word[j] = c;
                        if (word == endWord) return steps;
                        if (wordSet.count(word) && !visited.count(word)) {
                            visited.insert(word);
                            q.push(word);
                        }
                        word[j] = orig;
                    }
                }
            }
        }
        return 0;
    }
};

Complexity Analysis:

• Time Complexity: O(M² * N) where M is word length and N is dictionary size. For each of the N words, we try M * 26 substitutions and each string comparison/creation is O(M).
• Space Complexity: O(M * N) for the visited set and queue.

Where it breaks: the steps counter starts at 1 (the beginWord itself counts). When endWord is found at the next level, return steps (which has already been incremented for that level). Be careful with where you increment: increment before the inner loop, so the count is already updated when checking endWord.

Common Mistakes

• Returning steps without counting beginWord. The problem counts the number of words in the sequence, including begin and end. "hit" -> "hot" -> "dot" -> "dog" -> "cog" is 5 words.
• Not early-exiting when endWord is not in the dictionary. Without this check, BFS runs to completion and returns 0 anyway, but wastes time.
• Checking the entire word list as neighbors. This is O(N * M) per word instead of O(M * 26). At N = 5000 and M = 10, the difference is 5000 * 10 vs 10 * 26: the substitution approach is about 19x faster per word.

← All Problems