Difficulty: HardGraphs

Word Ladder

Problem in Plain English

Change one letter at a time to turn the begin word into the end word, using only words from the given list. Return the word count of the shortest such chain, or 0 when no chain exists.

Problem Statement

Given beginWord, endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord. Each neighbouring pair in the sequence must differ by exactly one letter, and every intermediate word must appear in wordList.

If no valid sequence exists, return 0. The length counts words, so a direct one-letter change has length 2.

Constraints

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

Examples

Example 1

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

The shortest chain is hit to hot to dot to dog to cog, which holds 5 words.

Example 2

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0

The end word cog is missing from the list, so no valid chain exists.

Example 3

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","cog"]
Output: 0

The target is present, but hit reaches only hot and dot. Dot and cog differ in two letters, so dictionary membership alone does not guarantee a chain.

Example 4

Input: beginWord = "a", endWord = "c", wordList = ["a","b","c"]
Output: 2

A direct change from a to c uses two words. The begin word may appear in the dictionary; marking it visited initially prevents revisiting it.

Intuition

Think of each allowed word as a vertex, with an edge between words differing in exactly one position. Every edge costs one change, so breadth-first search (BFS) explores shorter chains before longer ones. In Example 1, the layers are hit, hot, then dot and lot, then dog and log, then cog: five words. A wildcard such as *ot groups hot, dot and lot without comparing every pair. Once one BFS layer scans that bucket, all its words have already received their earliest possible discovery, so later visits can discard the bucket.

Approaches

Compare All Word Pairs

Solution Details

Reveal Compare All Word Pairs: intuition, complexity, and code

Intuition

Treat each word as a graph node and join neighbours that differ by one letter, then walk outward from the begin word level by level. Comparing every word against the whole list finds every neighbour, but the pairwise scan repeats the same letter checks, which the optimal approach replaces with pattern buckets.

Step-by-Step Logic

Queue hit at length 1 and mark it visited.
Pop hit and scan the list: only hot differs by one letter, so queue hot at length 2.
Pop hot and scan the list: dot and lot each differ by one letter, so queue both at length 3.
Pop dot then lot: they bring in dog and log at length 4.
Pop dog and queue cog at length 5. Pop the remaining length-4 word log, which adds nothing, then pop cog at length 5 and return 5. If the queue empties without finding the target, return zero.

Why It Works

The comparison accepts exactly words with one differing position, so every discovered edge is legal and scanning the whole list misses no legal neighbour. At the start of each outer iteration, the queue contains precisely the next unprocessed BFS layer, whose shortest chain length is len. Every newly discovered neighbour therefore has length len + 1; any shorter route would have discovered it in an earlier layer. Marking on enqueue prevents repeats without removing a shorter route. The first target removed from the queue has the minimum word count, and exhausting all reachable vertices proves no sequence exists.

Dry Run

Compare All Word Pairs: variable states at each step
len	Popped	New neighbours	Pending queue after pop	Seen after expansion
1	hit	hot	[hot]	{hit,hot}
2	hot	dot,lot	[dot,lot]	{hit,hot,dot,lot}
3	dot	dog	[lot,dog]	{hit,hot,dot,lot,dog}
3	lot	log	[dog,log]	{hit,hot,dot,lot,dog,log}
4	dog	cog	[log,cog]	all seven words
4	log	none; cog already seen	[cog]	unchanged
5	cog	target; no scan	[]	return 5

Complexity Analysis

Time Complexity

O(N^2 * M)

Space Complexity

O(N)

Let N be dictionary size and M word length. At most N + 1 dequeued words each scan N candidates, and comparing one pair costs O(M), giving O(N^2 M) worst-case time with expected hash-set operations. Queue and seen store O(N) references to existing immutable input strings, not copied word contents; counters use O(1). The input list is unchanged. This baseline makes neighbour lookup explicit but is slow on large reachable dictionaries.

Code

Solution.java

1import java.util.*;2
3class Solution {4    public int ladderLength(String beginWord, String endWord, List<String> wordList) {5        if (!wordList.contains(endWord)) {6            return 0;7        }8        Queue<String> queue = new LinkedList<>();9        Set<String> seen = new HashSet<>();10        queue.offer(beginWord);11        seen.add(beginWord);12        int len = 1;13        while (!queue.isEmpty()) {14            // Freeze the layer size: newly queued words belong to len + 1.15            int size = queue.size();16            for (int i = 0; i < size; i++) {17                String word = queue.poll();18                if (word.equals(endWord)) {19                    return len;20                }21                for (String w : wordList) {22                    if (!seen.contains(w) && differsByOne(word, w)) {23                        // Discover on enqueue so two parents cannot queue the same word.24                        seen.add(w);25                        queue.offer(w);26                    }27                }28            }29            len++;30        }31        return 0;32    }33
34    private boolean differsByOne(String a, String b) {35        int diff = 0;36        for (int i = 0; i < a.length(); i++) {37            if (a.charAt(i) != b.charAt(i)) {38                diff++;39                if (diff > 1) {40                    return false;41                }42            }43        }44        return diff == 1;45    }46}

Hints

Hint 1

The shortest chain in steps is a shortest path in an unweighted graph, so think level by level from the begin word.

Hint 2

Two words link when they differ in exactly one position, which defines the graph edges.

Hint 3

Wildcard buckets such as h*t group one-apart words together, so neighbours come from a map read instead of a full list scan.

Edge Cases

The end word is missing from the list, as in Example 2, so the answer is 0 before any search starts.
The begin word sits one letter from the end word, and the answer is 2 after a single expansion.
The end word is present but cut off from the begin word, so the queue drains and the answer is 0.

Common Mistakes and Interview Tips

Skipping the visited set, which lets the walk bounce between neighbours like hot and dot forever.
Keeping wildcard buckets after scanning them repeats member visits; remove each bucket to justify the faster bound.
Returning the level count instead of the word count, which undercounts the chain by one.

Key Takeaway

When edges are defined by a small local change, index items by their change patterns so neighbour lookup skips the pairwise scan.