Start learning free

LESSON 343 OF 348 · GRAPHS

Word Ladder in TypeScript: BFS with a Set and Letter Swaps

Practice O(N * L² * Σ) Read the full explanation

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the word list.

Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

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

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Example 2:

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

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

STEP 1 OF 16

Guided

Ctrl + Enter to check

TYPESCRIPT · GRAPHS

Word Ladder in TypeScript, explained

Problem overview

The method ladderLength receives beginWord, endWord and an array words. It returns the number of words in the shortest sequence from beginWord to endWord in which each step changes one letter and every word after the first is in words. If there is no such sequence, it returns 0.

For "hit" to "cog" with ["hot","dot","dog","lot","log","cog"], one shortest sequence is hit, hot, dot, dog, cog, so the answer is 5. If "cog" is not in the list, the answer is 0.

Approach: generate neighbours instead of searching for them

A breadth-first search (BFS) finds the shortest path when every step costs the same. It visits words in order of distance from beginWord, so the first time it reaches endWord, the distance is the shortest.

The simplest way to find the neighbours of a word is to compare it with every word in the list. That costs a full scan of words for every word the search expands. This lesson turns the problem around. A word of length L has only L * 25 possible one-letter variants, so instead of asking "which list words are close to this word?", the code builds each variant and asks "is it in the list?". To make that question cheap, the list is first copied into a Set, whose has method takes constant time on average.

The queue also changes. Instead of calling shift(), which moves every remaining element, the code leaves the array alone and walks through it with an index head. Words before head have been processed, and words from head on are waiting.

Step by step

Build wordSet with new Set(words). TypeScript infers Set<string>.
Create the queue as a string[] and a let head = 0. It must be let because it changes.
Create minDist as a Record<string, number>. It maps each reached word to the length of the shortest sequence ending there, and having a key means the word was already visited.
Seed the search. Push beginWord and give it distance 1, since a sequence of just that word has length 1.
Loop while head < queue.length. Anything at or beyond head is still waiting.
Take the next word with queue[head++]. Postfix ++ gives the old value of head and then adds 1, so one expression reads and advances.
Break at the target. Words come out in order of distance, so endWord's distance is already final.
Loop over each position i of the word, and inside it over the character codes 97 to 122, the codes of 'a' to 'z'. The counter c is a number.
Build the candidate from word.substring(0, i), then String.fromCharCode(c), then word.substring(i + 1). Strings are immutable, so a changed copy has to be assembled.
Skip non-words. If wordSet.has(nextWord) is false, continue.
Skip visited words. If nextWord in minDist, continue. This also skips word itself, which appears whenever c is the letter already at position i.
Record and enqueue. Set minDist[nextWord] to minDist[word] + 1 and push the word.
Return minDist[endWord] ?? 0 after the loop.

The solution in TypeScript

class Solution {
    ladderLength(beginWord: string, endWord: string, words: string[]): number {
        const wordSet = new Set(words);
        const queue: string[] = [];
        let head = 0;
        const minDist: Record<string, number> = {};
        queue.push(beginWord);
        minDist[beginWord] = 1;
        while (head < queue.length) {
            const word = queue[head++];
            if (word === endWord) {
                break;
            }
            for (let i = 0; i < word.length; i++) {
                for (let c = 97; c <= 122; c++) {
                    const nextWord = word.substring(0, i) + String.fromCharCode(c) + word.substring(i + 1);
                    if (!wordSet.has(nextWord)) {
                        continue;
                    }
                    if (nextWord in minDist) {
                        continue;
                    }
                    minDist[nextWord] = minDist[word] + 1;
                    queue.push(nextWord);
                }
            }
        }
        return minDist[endWord] ?? 0;
    }
}

TypeScript details worth knowing:

Record<string, number> is a type alias for an object whose keys are strings and whose values are numbers. It exists only for the compiler; at run time minDist is a plain object.
?? versus ||. A missing key reads as undefined, and undefined ?? 0 is 0. Unlike ||, the operator ?? replaces only null and undefined, not other falsy values such as 0. That makes it the more precise choice for "use a default when absent".
Character codes. String.fromCharCode(97) is "a". Looping over numbers and converting each one is a compact way to run through the alphabet.
substring(start, end) excludes the character at end, and substring(start) runs to the end of the string. Together the two calls drop exactly the character at i.
The in operator searches the prototype chain. "constructor" in {} is true. If a word in the list were "constructor", this solution would skip it as already visited, and minDist["constructor"] would read back the Object function. A Map doesn't have this problem. It is the edge of an otherwise sound solution, not something the lesson's test words hit.
Reading past the queue. queue[head++] is safe because the loop condition guarantees head < queue.length. Types would not catch a mistake here: an out-of-range read just gives undefined at run time.

Complexity

Let N be the number of words and L their length.

Time: O(N * L²), with a factor of 26 for the alphabet. Each word enters the queue at most once. Expanding it tries L * 26 candidates. Building a candidate copies L characters, and hashing it for has and in reads them again, so each candidate costs O(L). That makes L * 26 * L work per word. This beats the O(N² * L) of comparing every pair when the list is much longer than the words.

Space: O(N * L). The set, the queue and minDist each hold at most the list's words.

Edge cases and common mistakes

Target not in the list. No variant ever equals it, so it never gets a distance and the method returns 0.
Start word not in the list. Allowed. It is queued directly, and only its variants must be in the set.
Re-adding the word itself. When c equals the current letter, the candidate is word. If word is in the list, only the minDist check stops it from being queued again.
Distance 0 for the start. That gives answers one too small, because the lesson counts words, not changes.
Using c as a letter. Adding the number c to a string appends its digits, so String.fromCharCode(c) is needed.
Looping to 123. c <= 122 is inclusive; c < 122 would never try 'z'.

Testing

"hit" to "cog" with ["hot","dot","dog","lot","log","cog"] gives 5.
The same words without "cog" give 0.
"hit" to "hot" with ["hot"] gives 2.
"a" to "c" with ["a","b","c"] gives 2.

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free