Problem overview
The method ladderLength(beginWord, endWord, words) finds the shortest chain of words from beginWord to endWord. Each step changes exactly one letter, and every word you step to must be in the list words. The result is the number of words in the chain, counting both ends, or 0 when no chain exists. All words have the same length and use lowercase letters only.
With beginWord = "hit", endWord = "cog" and words = ["hot", "dot", "dog", "lot", "log", "cog"], one shortest chain is hit -> hot -> dot -> dog -> cog. It has 5 words, so the answer is 5. Without "cog" in the list, the end word can never be reached, and the answer is 0. Note that beginWord itself does not have to be in the list.
Approach: a shortest path in an implicit graph
Think of each word as a node, with an edge between two words that differ in one letter. Then the problem asks for the shortest path between two nodes in an unweighted graph, and the standard tool for that is breadth-first search (BFS). BFS explores words in rings: first everything one step away from the start, then everything two steps away, and so on. The first time it reaches endWord, it has arrived by the fewest steps.
The graph is not given, so you need a way to find the neighbours of a word. The obvious way is to compare the word with every other word, which costs a comparison per pair. The lesson uses a better trick: replace one letter with a wildcard * to make a pattern. The word "hot" has the patterns "*ot", "h*t" and "ho*". Two words differ in exactly one letter if and only if they share a pattern: "hot" and "dot" both have "*ot". So if you group words by their patterns up front, the neighbours of any word are the words in its patterns' groups.
For the first example the groups include "*ot" with hot, dot and lot, "do*" with dot and dog, and "*og" with dog, log and cog. The word "hit" has the patterns "*it", "h*t" and "hi*", and the group for "h*t" contains "hot", so BFS reaches hot first. From hot, the pattern "*ot" leads to dot and lot (hot itself is skipped because it was already reached). The next ring contains dog and log, and the one after that contains cog, at distance 5.
Step by step
- Create
graphas an empty object. It maps each pattern to the list of words that match it. - Loop over every word and every position
iin it. A helper,getStarWord(word, i), returns the pattern: the part before indexi, then"*", then the part after it, each cut withsubstring. - Add the word to its pattern's list. The expression
[...graph[starWord] || [], word]takes the existing list, or an empty array when the key is missing (reading a missing key givesundefined, andundefined || []is[]), and builds a new array withwordadded. - Create a queue for the BFS, using the
Queuefrom the algorithms library that the lesson loads. An array'sshift()would beO(n), because it moves every remaining element. - Create
minDist, an object from word to the length of the shortest chain that ends in it. Having an entry also means "already reached", so it doubles as the visited set. - Seed the search: push
beginWordand set its distance to 1. The answer counts words, not changes, so the start is 1. - Run while the queue is not empty. Take the front word. If it equals
endWord, stop: BFS removes words from the queue in order of distance, so the stored distance is already the shortest. - Visit the neighbours. For each position
i, compute the pattern and loop over the words stored under it ingraph. Use|| []so that a missing pattern gives an empty loop. - Skip words already reached, with
!(nextWord in minDist). The parentheses are needed because!binds tighter thanin. The current word also belongs to its own pattern, but it has an entry, so it is skipped. - Record and queue new words. Set
minDist[nextWord] = minDist[word] + 1and push the word. Recording the distance when a word is queued, not when it is taken out, prevents the same word from entering the queue twice. - Return the answer:
minDist[endWord] || 0. A word that was never reached has no entry, which reads asundefined, andundefined || 0is 0.
The solution in JavaScript
var algorithms = require('algorithms');
class Solution {
getStarWord(word, i) {
return word.substring(0, i) + '*' + word.substring(i + 1);
}
ladderLength(beginWord, endWord, words) {
let graph = {};
for (let word of words) {
for (let i = 0; i < word.length; i++) {
let starWord = this.getStarWord(word, i);
graph[starWord] = [...graph[starWord] || [], word];
}
}
let queue = new algorithms.DataStructures.Queue();
let minDist = {};
queue.push(beginWord);
minDist[beginWord] = 1;
while (!queue.isEmpty()) {
let word = queue.pop();
if (endWord == word) {
break;
}
for (let i = 0; i < word.length; i++) {
let starWord = this.getStarWord(word, i);
for (let nextWord of graph[starWord] || []) {
if (!(nextWord in minDist)) {
minDist[nextWord] = minDist[word] + 1;
queue.push(nextWord);
}
}
}
}
return minDist[endWord] || 0;
}
}
JavaScript details to notice:
- The queue's method names differ from an array's. On the library
Queue,pushadds to the back andpopremoves from the front. On a plain array,poptakes from the back, which would turn the BFS into a depth-first search and give wrong distances. - Precedence in
[...graph[starWord] || [], word]. The spread applies to the whole expressiongraph[starWord] || [], so the existing list, or an empty one, is copied into the new array. - Spreading copies the list each time. Appending with
pushwould add in place. For lists of a few words the difference does not show. - Objects as dictionaries inherit properties.
graphandminDistare plain objects, so"constructor" in minDististrueeven when it was never added. WithbeginWord = "constructon",endWord = "constructor"andwords = ["constructor"], the solution skips the end word and returns a function instead of 2. Ordinary test words don't trigger this, but aMap(withget,setandhas) orObject.create(null)would avoid it.
Complexity
Let N be the number of words and L their length. Building the groups creates L patterns for each word, and each pattern is a string of length L, so that costs O(N * L²). The BFS takes each word out of the queue once and, for each of its L patterns, scans the matching group. When groups are small, this is also about O(N * L²). If many words share one pattern, the group scans dominate, and in the worst case the total can approach O(N² * L). The groups store up to N * L patterns of L characters each, so the space is about O(N * L²).
The simple alternative, comparing a word with every other word to find neighbours, costs O(L) per pair, or O(N² * L) in total. The pattern groups avoid that in typical inputs.
Edge cases and common mistakes
- The end word missing from the list. It never enters the queue, so
minDist[endWord]isundefinedand the method returns 0. - Counting changes instead of words. The first example has 4 changes but the answer is 5. That is why
minDist[beginWord]starts at 1. - Marking words as visited too late. If the distance were recorded when a word is taken out of the queue, the same word could be queued many times, which wastes time and can change the stored distance.
- Using an array with
shift()as the queue. It works, but eachshift()moves the remaining elements, so a large queue gets slow. - Forgetting
|| []on a missing pattern. A word reached from the begin word may have a pattern that no word in the list has.graph[starWord]is thenundefined, and looping overundefinedthrows aTypeError. - The begin word is not in the list. This is allowed. It is not in the graph, but its patterns lead into it, and the search starts from it directly.
Testing
Try these in the editor, with words as the third argument:
"hit","cog"with["hot","dot","dog","lot","log","cog"]returns5."hit","cog"with["hot","dot","dog","lot","log"]returns0."hit","hot"with["hot"]returns2."hot","dog"with["hot","dog"]returns0, since hot and dog differ in two letters.
