Problem overview
The method ladderLength receives beginWord, endWord and an array words. It returns the number of words in the shortest sequence that starts at beginWord, ends at endWord, changes one letter per step, and uses only words from words after the first. If no such sequence exists, it returns 0.
For "hit" to "cog" with ["hot","dot","dog","lot","log","cog"], the sequence hit, hot, dot, dog, cog has five words, so the answer is 5. Without "cog" in the list, the answer is 0.
Approach: search from both ends
A plain breadth-first search (BFS) from beginWord expands level after level until it reaches endWord. When every word has many neighbours, each level is much larger than the one before, and the last levels are the expensive ones. Starting a second search from endWord and stopping when the two searches meet means each search only has to go about half as deep, and the levels at that depth are far smaller.
The neighbours come from a map of patterns. Replacing one position of a word with * gives a pattern, such as "*ot" for "hot". Words that share a pattern differ in exactly one letter, so looking up the patterns of a word yields its neighbours without comparing against the whole list.
Each side keeps its own queue and its own distance map, which also serves as that side's visited set. Each distance counts the words from that side's starting word, both ends included. When one side steps onto a word that the other side has already reached, the two searches meet. The answer is the sum of the first side's distance to the current word and the other side's distance to the neighbour. The two words are different, so no word is counted twice.
Two details keep the answer shortest. First, the searches expand one whole level at a time. Expanding single words could let the searches meet through a longer sequence while a shorter one is still waiting in a queue. Second, each pass expands the side with the shorter queue, since a smaller level is cheaper to grow.
Step by step
- Return early. If
wordsdoes notincludeendWord, return 0. No sequence can end at a word outside the list, and the second search starts fromendWord. - Write
getStarWord, which takes a word and a position and returns the word with that position replaced by*, using twosubstringcalls. - Write
buildGraph, which takeswordsand returns aMap<string, string[]>. For every word and every position it computes the pattern, creates an empty array under that key if the map doesn't have one yet, and pushes the word onto it. The!aftergetis a non-null assertion, valid because the check above it guarantees the key exists. It then returns the map. - Prepare both searches in
ladderLength. Callthis.buildGraph(words), then createbeginQueueandendQueueasstring[]andbeginMinDistandendMinDistasMap<string, number>. Push each starting word into its own queue and set its distance to 1. - Declare
let result = 0to hold what each level expansion returns. - Loop while both queues are non-empty. If either side runs out of words, the searches can never meet.
- Write
processLevelwith parametersgraph,queue,minDistandotherMinDist. It expands one whole level of the side it is given. - Freeze the level. Store
queue.lengthinlevelSizeand loopkfrom 0 tolevelSize. Words pushed during this call belong to the next level and must wait for the next call. - Dequeue a word and visit each of its patterns. For every
nextWordingraph.get(starWord) || [], handle two cases in this order. IfotherMinDistcontains it, the searches met: returnminDist.get(word)! + otherMinDist.get(nextWord)!. Otherwise, ifminDisthasn't seen it, set its distance tominDist.get(word)! + 1and push it. - Report no meeting. If the loops end, return 0. A real sequence has at least two words, so 0 can't be mistaken for an answer.
- Choose a side. In the main loop, if
beginQueue.length <= endQueue.length, expand the begin side; otherwise expand the end side with the roles swapped. Use<=so the begin side goes first on a tie. - Return when
result > 0, and return 0 after the loop.
The solution in TypeScript
class Solution {
getStarWord(word: string, i: number): string {
return word.substring(0, i) + '*' + word.substring(i + 1);
}
buildGraph(words: string[]): Map<string, string[]> {
const graph = new Map<string, string[]>();
for (const word of words) {
for (let i = 0; i < word.length; i++) {
const starWord = this.getStarWord(word, i);
if (!graph.has(starWord)) {
graph.set(starWord, []);
}
graph.get(starWord)!.push(word);
}
}
return graph;
}
processLevel(graph: Map<string, string[]>, queue: string[], minDist: Map<string, number>, otherMinDist: Map<string, number>): number {
const levelSize = queue.length;
for (let k = 0; k < levelSize; k++) {
const word = queue.shift()!;
for (let i = 0; i < word.length; i++) {
const starWord = this.getStarWord(word, i);
for (const nextWord of graph.get(starWord) || []) {
if (otherMinDist.has(nextWord)) {
return minDist.get(word)! + otherMinDist.get(nextWord)!;
}
if (!minDist.has(nextWord)) {
minDist.set(nextWord, minDist.get(word)! + 1);
queue.push(nextWord);
}
}
}
}
return 0;
}
ladderLength(beginWord: string, endWord: string, words: string[]): number {
if (!words.includes(endWord)) {
return 0;
}
const graph = this.buildGraph(words);
const beginQueue: string[] = [];
const endQueue: string[] = [];
const beginMinDist = new Map<string, number>();
const endMinDist = new Map<string, number>();
beginQueue.push(beginWord);
endQueue.push(endWord);
beginMinDist.set(beginWord, 1);
endMinDist.set(endWord, 1);
let result = 0;
while (beginQueue.length > 0 && endQueue.length > 0) {
if (beginQueue.length <= endQueue.length) {
result = this.processLevel(graph, beginQueue, beginMinDist, endMinDist);
} else {
result = this.processLevel(graph, endQueue, endMinDist, beginMinDist);
}
if (result > 0) {
return result;
}
}
return 0;
}
}
TypeScript details worth knowing:
Mapinstead of an object. AMaphas realhas,getandsetmethods and no inherited keys, so a word like"constructor"behaves like any other key. With a plain object and theinoperator, it would not.getmay returnundefined. With strict null checks on, its type isV | undefined, so the code adds!where it knows the key exists. The!is erased when the file is compiled and checks nothing at run time: if the key were missing, the value would beundefinedand the sum would beNaN.|| []for a missing pattern. It stands in an empty array, so thefor...ofloop runs zero times.- Shared state. Arrays and maps are passed by reference, so
processLevelpushes into the caller's queue and fills the caller's map. Nothing is copied or returned for them. - Swapped roles. The same method serves both sides because its last two parameters are "mine" and "theirs". The end side calls it with the maps in the opposite order.
shift()moves elements. Each call costs time proportional to the queue length. The lesson accepts that for simplicity; an index into the array would avoid it.
Complexity
Let N be the number of words and L their length.
Time: O(N * L²) for typical inputs. Building the graph costs N * L patterns, each O(L) to build and hash. Each side queues a word at most once. Expanding a word looks at L patterns and their buckets. As with the one-sided pattern search, a huge bucket can push the worst case towards O(N²) checks. The point of searching from both ends is not a better worst case but far fewer words visited in practice: each search stops at about half the depth, where the levels are smaller.
Space: O(N * L²). The graph holds up to N * L patterns of length L, and the queues and maps hold at most the words of the list plus the two ends.
Edge cases and common mistakes
- Start word not in the list. This is allowed. The tie rule matters here: with
beginWord = "hot",endWord = "dot"andwords = ["dot"], the answer is 2 because the begin side expands first. If the end side went first on a tie, it would find only"dot"itself, never reach"hot", and run out of words. With<instead of<=, the lesson's code returns 0 for that input. - Target not in the list. The early return handles it before any search work.
- Expanding word by word. Without the
levelSizesnapshot, a side could keep going into the next level, and the first meeting might not be the shortest. - Looping to
queue.length. The length grows during the loop, sok < queue.lengthwould never stop at the end of the level. - Adding the distances wrongly. Both distances count their own starting word. Adding 1 on top of the sum, or subtracting 1, gives the wrong length.
Testing
"hit"to"cog"with["hot","dot","dog","lot","log","cog"]gives5.- The same words without
"cog"give0. "hot"to"dot"with["dot"]gives2."a"to"c"with["a","b","c"]gives2.