10.5 Word Ladder

10.5.1 Problem Metadata

10.5.2 Description

Given a begin word, end word, and a dictionary, return the length of the shortest transformation sequence from begin to end such that only one letter changes per step and every intermediate word exists in the dictionary. Return 0 if no sequence exists.

10.5.3 Examples

Input: beginWord = "hit", endWord = "cog",
       wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: "hit" -> "hot" -> "dot" -> "dog" -> "cog"

10.5.4 Constraints

  • All words have the same length
  • Words consist of lowercase Englc-lish letters
  • wordList contains no duplicates

10.5.5 Solution - BFS Over Word Mutations

10.5.5.1 Walkthrough

Perform BFS from beginWord. Each step generates all words formed by replacing one letter with 'a'..'z'. Newly discovered dictionary entries are enqueued with distance level + 1. The first time endWord is dequeued we have the shortest length.

10.5.5.2 Analysis

  • Time Complexity: O(26 * L * N) where L is word length and N is dictionary size
  • Space Complexity: O(N)

10.5.5.3 Implementation Steps

  1. Insert dictionary into a Set for O(1) lookups.
  2. Initialize BFS queue with beginWord and level 1.
  3. For each dequeued word, mutate every position with every letter.
  4. If mutation equals endWord, return level + 1.
  5. If mutation existed in the dictionary, remove it and enqueue with incremented level.
  6. Return 0 when the queue empties without finding endWord.

10.5.5.4 Code - Java

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> dict = new HashSet<>(wordList);
    if (!dict.contains(endWord)) {
        return 0;
    }
    Queue<String> queue = new LinkedList<>();
    queue.offer(beginWord);
    int level = 1;

    while (!queue.isEmpty()) {
        for (int i = queue.size(); i > 0; i--) {
            String word = queue.poll();
            if (word.equals(endWord)) {
                return level;
            }
            char[] chars = word.toCharArray();
            for (int pos = 0; pos < chars.length; pos++) {
                char original = chars[pos];
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == original) continue;
                    chars[pos] = c;
                    String next = new String(chars);
                    if (dict.remove(next)) {
                        queue.offer(next);
                    }
                }
                chars[pos] = original;
            }
        }
        level++;
    }
    return 0;
}