Hard java coding

How do you find the length of the shortest word ladder?

The 30 second answer

I model this as BFS on an unweighted word graph. If the end word is not in the list I return zero. I bucket words under wildcard patterns like h*t, so one-letter neighbors share a pattern. Search starts at the begin word, visits each word once, and returns the word count when it reaches the end. That's roughly O(N L²). A follow-up is bidirectional BFS.

The usual statement is LeetCode's Word Ladder problem. You are given beginWord, endWord and a dictionary wordList. A legal step changes exactly one letter, and every intermediate word must be in the list; beginWord itself does not have to be. Return the number of words in the shortest such sequence, or 0 if none exists. The official constraints also state that beginWord and endWord differ, that every word has the same length, and that the list has no duplicates.

Why BFS. Each legal step has the same cost, so the first time a search reaches endWord is a shortest path. In an unweighted graph, breadth-first search is the standard way to compute that path; Sedgewick and Wayne prove that BFS finds a shortest path by number of edges and runs in time proportional to the vertices and edges in the worst case.

Wildcard buckets. Comparing every word to every other word is too slow. Instead, group words that differ at one position under a shared pattern. For hot the three patterns are *ot, h*t and ho*. Any two words that differ by a single letter fall into the same bucket, so the neighbors of a word are the other members of its L buckets. The official first example starts at hit; the pattern h*t contains hot, and one shortest sequence is hit -> hot -> dot -> dog -> cog, which has length 5. If cog is missing from the list, there is no legal sequence and the answer is 0.

Edge cases to say out loud. If endWord is not in the list, return 0 immediately. Mark a word visited when it is first enqueued, not when it is dequeued, so the same word is not expanded twice. The value you return counts words, not hops: the five-word official sequence has four transformations.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class WordLadder {
    // Shortest transformation length, or 0 if none exists.
    static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) return 0;

        Map<String, List<String>> buckets = new HashMap<>();
        for (String word : dict) {
            for (String pattern : patterns(word)) {
                buckets.computeIfAbsent(pattern, k -> new ArrayList<>()).add(word);
            }
        }

        Queue<String> queue = new ArrayDeque<>();
        Set<String> seen = new HashSet<>();
        queue.add(beginWord);
        seen.add(beginWord);
        int length = 1; // beginWord counts as one word in the sequence
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                String cur = queue.remove();
                if (cur.equals(endWord)) return length;
                for (String pattern : patterns(cur)) {
                    for (String next : buckets.getOrDefault(pattern, List.of())) {
                        if (seen.add(next)) queue.add(next);
                    }
                }
            }
            length++;
        }
        return 0;
    }

    // "hot" -> [*ot, h*t, ho*]
    static List<String> patterns(String word) {
        List<String> out = new ArrayList<>(word.length());
        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char saved = chars[i];
            chars[i] = '*';
            out.add(new String(chars));
            chars[i] = saved;
        }
        return out;
    }

    public static void main(String[] args) {
        System.out.println(ladderLength("hit", "cog",
            List.of("hot", "dot", "dog", "lot", "log", "cog"))); // 5
        System.out.println(ladderLength("hit", "cog",
            List.of("hot", "dot", "dog", "lot", "log")));        // 0
    }
}

Complexity. Let N be the size of wordList and L the word length. Building the pattern map creates L patterns of length L for each word, which is O(N L²). During BFS each word is dequeued at most once; generating its L patterns costs O(L) each, and every word appears in L buckets, so scanning neighbors over the whole search is O(N L). Overall time is therefore O(N L²). The map stores O(N L) keys of length L, so extra space is also O(N L²), plus the queue and the visited set.

Follow-up: bidirectional BFS. Grow two frontiers, one from beginWord and one from endWord, often expanding the smaller side first. The first time a word already reached from one side is reached from the other, you have a shortest path: add the two distances and subtract one so the meeting word is not counted twice. The worst-case bound does not change, but the search often visits fewer words than a one-sided BFS.

Sources (2)
  1. LeetCode 127: Word Ladderleetcode.com
  2. Sedgewick and Wayne, Algorithms, 4th edition, section 4.1, Breadth-first searchalgs4.cs.princeton.edu