Word Ladder

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

• Every adjacent pair of words differs by a single letter.
• Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
• sk == endWord

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

Example 1:

Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”] Output: 5 Explanation: One shortest transformation sequence is “hit” -> “hot” -> “dot” -> “dog” -> cog”, which is 5 words long.

Example 2:

Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”] Output: 0 Explanation: The endWord “cog” is not in wordList, therefore there is no valid transformation sequence.

Constraints:

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

Approach: Bidirectional BFS

Algorithm

1. Convert wordList into a set for O(1) membership checks
2. Run BFS from both beginWord and endWord, alternating between the two frontiers to reduce search space
3. For each word in the smaller frontier, try changing every position to each of the 26 letters; if the new word is in the set and not yet visited on that side, enqueue it
4. Whenever a word is reached from both sides, the distance is the sum of the two levels; if the frontiers are exhausted without meeting, return 0

Time & Space Complexity

• Time Complexity: O(M² * N) - N words of length M; each word produces M*26 neighbors and set lookups are O(M)
• Space Complexity: O(N * M) - the visited maps and queues

Java Implementation

import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Set;

public class WordLadder {

    /**
     * Return the number of words in the shortest transformation sequence.
     * @param beginWord Start word
     * @param endWord Target word
     * @param wordList Dictionary
     * @return Length of the shortest sequence, or 0
     */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) {
            return 0;
        }

        Queue<String> beginQueue = new ArrayDeque<>();
        Queue<String> endQueue = new ArrayDeque<>();
        Set<String> beginVisited = new HashSet<>();
        Set<String> endVisited = new HashSet<>();

        beginQueue.offer(beginWord);
        endQueue.offer(endWord);
        beginVisited.add(beginWord);
        endVisited.add(endWord);

        int level = 1;
        while (!beginQueue.isEmpty() && !endQueue.isEmpty()) {
            if (beginQueue.size() > endQueue.size()) {
                Queue<String> tempQ = beginQueue;
                beginQueue = endQueue;
                endQueue = tempQ;
                Set<String> tempS = beginVisited;
                beginVisited = endVisited;
                endVisited = tempS;
            }

            int size = beginQueue.size();
            for (int i = 0; i < size; i++) {
                String word = beginQueue.poll();
                for (String next : getNeighbors(word, wordSet)) {
                    if (endVisited.contains(next)) {
                        return level + 1;
                    }
                    if (!beginVisited.contains(next)) {
                        beginVisited.add(next);
                        beginQueue.offer(next);
                    }
                }
            }
            level++;
        }

        return 0;
    }

    private List<String> getNeighbors(String word, Set<String> wordSet) {
        java.util.List<String> neighbors = new java.util.ArrayList<>();
        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char original = chars[i];
            for (char c = 'a'; c <= 'z'; c++) {
                if (c == original) {
                    continue;
                }
                chars[i] = c;
                String candidate = new String(chars);
                if (wordSet.contains(candidate)) {
                    neighbors.add(candidate);
                }
            }
            chars[i] = original;
        }
        return neighbors;
    }

    // Test method
    public static void main(String[] args) {
        WordLadder wl = new WordLadder();
        System.out.println("Input: beginWord = \"hit\", endWord = \"cog\", wordList = [\"hot\",\"dot\",\"dog\",\"lot\",\"log\",\"cog\"]");
        System.out.println("Output: " + wl.ladderLength("hit", "cog",
                List.of("hot", "dot", "dog", "lot", "log", "cog"))); // Expected: 5

        System.out.println("Input: beginWord = \"hit\", endWord = \"cog\", wordList = [\"hot\",\"dot\",\"dog\",\"lot\",\"log\"]");
        System.out.println("Output: " + wl.ladderLength("hit", "cog",
                List.of("hot", "dot", "dog", "lot", "log"))); // Expected: 0
    }
}

Example Walkthrough

For beginWord = "hit", endWord = "cog":

1. Begin frontier: {hit} at level 1; end frontier: {cog}
2. Expand hit -> hot (level 2); expand cog -> log, dog (level 2)
3. Expand hot -> dot, lot (level 3); both sides grow
4. Expand dot/dog side until frontiers meet at dog/cog: hit->hot->dot->dog->cog, 5 words

Key Points

1. BFS Guarantees Shortest: Level-by-level exploration finds the minimum number of transformations
2. Bidirectional Search: Expanding from both ends shrinks the search space dramatically
3. Word Set: Membership checks against the dictionary are O(1) with a hash set
4. Neighbor Generation: Every word has at most M*25 neighbors, each a single-letter change
5. Meeting Condition: A word visited by both sides terminates the search with the summed distance