Problem overview
The method ladderLength receives a start word beginWord, a target word endWord and an array words. It returns the length of the shortest sequence of words that starts at beginWord, ends at endWord, changes exactly one letter per step, and uses only words from words after the first one. The length counts the words in the sequence, not the number of changes. If no such sequence exists, the method returns 0.
In the first example, "hit" becomes "hot", then "dot", "dog" and "cog". That is five words, so the answer is 5. In the second example "cog" is missing from the list, so the answer is 0.
Approach: breadth-first search
Think of every word as a node, with an edge between two words that differ in exactly one position. The question becomes: how many nodes are on the shortest path from beginWord to endWord? In a graph where every edge costs the same, breadth-first search (BFS) answers this. It visits all words one step away, then all words two steps away, and so on, so the first time it reaches a word, it has reached it by a shortest route.
The search needs two things. A queue holds the words that have been reached but not yet expanded, in the order they were reached. A distance map, minDist, stores for each reached word the length of the shortest sequence that ends there. A word with an entry has been seen already, so the same map doubles as the visited set.
This lesson finds the neighbours of a word the simple way: it compares the word against every entry of words. That costs a scan of the whole list for each dequeued word. Other lessons on this problem build the neighbours faster; this one keeps the idea as plain as possible.
Step by step
- Create the queue as an empty
string[]. - Create
minDistas an object with the index signature{ [key: string]: number }, which says that any string key holds a number. - Seed the search. Push
beginWordand set its distance to 1, because a sequence holding only the first word has length 1. - Loop while the queue is not empty.
- Dequeue the front word with
shift(). The!after the call is a non-null assertion: with strict null checks on,shift()is typedstring | undefined, and the loop condition guarantees a word is there. - Stop at the target. If the word equals
endWord, break. Words leave the queue in order of distance, so the stored distance is already the shortest. - Scan every candidate in
wordswithfor...of. - Keep only true neighbours. Assume a helper
numOfChangesthat counts the positions where two words differ, and skip any candidate where the count is not exactly 1. A count of 0 is the same word, and 2 or more is too far away. - Skip words already reached. If
nextWord in minDist, an earlier and at-least-as-short sequence got there first. - Record and enqueue. Set
minDist[nextWord]tominDist[word] + 1and push the word. Storing the distance at enqueue time, not at dequeue time, keeps a word from entering the queue twice. - Return the answer after the loop: the stored distance for
endWord, or 0 if it was never reached. - Write
numOfChangeswith twostringparameters and anumberresult. It keeps a counterdifferencesstarting at 0 and loops over every index offirst. All words have the same length, so the same index is valid insecond. It increments the counter when the characters differ, and returns it.
The solution in TypeScript
class Solution {
numOfChanges(first: string, second: string): number {
let differences = 0;
for (let i = 0; i < first.length; ++i) {
if (first[i] !== second[i]) {
differences++;
}
}
return differences;
}
ladderLength(beginWord: string, endWord: string, words: string[]): number {
const queue: string[] = [];
const minDist: { [key: string]: number } = {};
queue.push(beginWord);
minDist[beginWord] = 1;
while (queue.length > 0) {
const word = queue.shift()!;
if (word === endWord) {
break;
}
for (const nextWord of words) {
if (this.numOfChanges(word, nextWord) !== 1) {
continue;
}
if (nextWord in minDist) {
continue;
}
minDist[nextWord] = minDist[word] + 1;
queue.push(nextWord);
}
}
return minDist[endWord] || 0;
}
}
TypeScript details worth knowing:
- Types are erased.
string[],{ [key: string]: number }and the!disappear when the file is compiled to JavaScript. At run timeminDistis an ordinary object andqueuean ordinary array. - Missing keys read as
undefined.minDist[endWord]isundefinedwhen the target was never reached, andundefined || 0is 0. The same expression would also turn a stored distance of 0 into 0, which is harmless here because every stored distance is at least 1. inlooks at the prototype chain too."constructor" in {}istrue, because every object inherits that property. If the word list contains"constructor", the checknextWord in minDistwould wrongly skip it, and readingminDist["constructor"]would give back theObjectfunction instead of a distance. For this lesson's test words that doesn't matter, but aMapavoids the trap entirely, and a later lesson on this problem uses one.shift()is not free. Removing the first element of an array shifts the rest down, so a dequeue costs time proportional to the queue length. Here every dequeue is followed by a scan of the whole list, which costs at least as much, so it does not change the overall complexity.this.numOfChanges. A method of the class must be called throughthis; a barenumOfChanges(...)would look for a function outside the class.
Complexity
Let N be the number of words and L the length of each word.
Time: O(N² * L). Each word enters the queue at most once, because its distance is stored the moment it is queued. For each dequeued word the loop compares it against all N candidates, and each comparison costs O(L).
Space: O(N * L). The queue and minDist together hold at most one entry per word, plus the words themselves.
Edge cases and common mistakes
- Target not in the list. The search never reaches it,
minDist[endWord]is missing, and the method returns 0. - Start word not in the list. That's fine: the start only has to be queued, not found.
ladderLength("hit", "hot", ["hot"])returns 2. - Counting changes instead of words. Starting
minDist[beginWord]at 0 makes every answer one too small. - Accepting zero or many differences. A neighbour must differ in exactly one position. Testing only
numOfChanges(...) <= 1accepts the word itself. - Setting the distance on dequeue. The same word could then be queued several times by different neighbours, and the queue grows needlessly.
- Using
==or!=. They work on strings and numbers here, but===and!==are the habit to keep.
Testing
With words = ["hot","dot","dog","lot","log","cog"]:
"hit"to"cog"gives5."hit"to"hot"gives2.numOfChanges("hit", "hot")gives1,numOfChanges("hit", "hit")gives0andnumOfChanges("hit", "cog")gives3.
With the same list minus "cog", "hit" to "cog" gives 0.