Start learning free

LESSON 344 OF 348 · GRAPHS

Word Ladder in TypeScript: BFS with Wildcard Patterns

Practice O(N * L2) 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:

  1. Only one letter can be changed at a time.
  2. 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 21
    Ctrl + Enter to check

    TYPESCRIPT · GRAPHS

    Word Ladder in TypeScript, explained

    Problem overview

    The method ladderLength takes beginWord, endWord and an array words. It returns how many words the shortest sequence from beginWord to endWord contains, where each step changes one letter and each new word must be in words. When no 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: group words by pattern

    Breadth-first search (BFS) gives the shortest path when every step costs the same, and its main cost is finding the neighbours of each word. Comparing a word with the whole list is slow. Trying all 26 letters at each position is better, but most of those variants aren't words at all.

    This lesson uses a different idea. Replace one position of a word with * to get a pattern: "hot" gives "*ot", "h*t" and "ho*". Two words differ in exactly one letter precisely when they share a pattern, because they agree everywhere except at the starred position. So if every pattern is mapped to the list of words that produce it, the neighbours of a word are the union of the lists under its own patterns. For the example list, "*ot" holds hot, dot and lot, and "*og" holds dog, log and cog.

    The map is built once, and then the BFS never scans the whole list again. It only looks at the buckets for the word it is expanding. A word is also in its own buckets, but its distance is already stored by then, so it is not queued again.

    Step by step

    1. Create graph as an object with the index signature { [key: string]: string[] }. It maps each pattern to its words.
    2. Loop over words with for...of, and over every position i of each word.
    3. Write getStarWord as a method with parameters word: string and i: number. It returns the part before index i, then "*", then the part after, using substring.
    4. Fill the buckets. Call this.getStarWord(word, i) to get starWord. Then set graph[starWord] to its current value or a new empty array with ||, and push word onto the result. The assignment is an expression whose value is the array, so the parentheses let .push(word) apply to it.
    5. Set up the BFS. Create the queue and a minDist object, push beginWord and give it distance 1, since a sequence of one word has length 1.
    6. Loop while the queue has words, taking the front with shift()!.
    7. Break when the word equals endWord. Words leave the queue in order of distance, so its stored distance is already the shortest.
    8. Visit each pattern of the current word. Loop over positions again and compute starWord.
    9. Visit the bucket. Loop over graph[starWord] || []. The || [] makes a missing pattern behave as an empty list.
    10. Enqueue unseen words. If !(nextWord in minDist), set minDist[nextWord] to minDist[word] + 1 and push it. The parentheses are required because ! binds tighter than in.
    11. Return minDist[endWord] || 0.

    The solution in TypeScript

    class Solution {
    getStarWord(word: string, i: number): string {
        return word.substring(0, i) + "*" + word.substring(i + 1);
    }

    ladderLength(beginWord: string, endWord: string, words: string[]): number {
        const graph: { [key: string]: string[] } = {};
        for (const word of words) {
            for (let i = 0; i < word.length; i++) {
                const starWord = this.getStarWord(word, i);
                (graph[starWord] = graph[starWord] || []).push(word);
            }
        }
        const queue: string[] = [];
        const minDist: { [key: string]: number } = {};
        queue.push(beginWord);
        minDist[beginWord] = 1;
        while (queue.length > 0) {
            const word = queue.shift()!;
            if (endWord === word) {
                break;
            }
            for (let i = 0; i < word.length; i++) {
                const starWord = this.getStarWord(word, i);
                for (const nextWord of graph[starWord] || []) {
                    if (!(nextWord in minDist)) {
                        minDist[nextWord] = minDist[word] + 1;
                        queue.push(nextWord);
                    }
                }
            }
        }
        return minDist[endWord] || 0;
    }
}

    TypeScript details worth knowing:

    • The one-line bucket update. (graph[starWord] = graph[starWord] || []).push(word) does three things: reads the bucket (or undefined for a new pattern), stores it back, and pushes. The assignment evaluates to the array that was stored, so push acts on the real bucket in graph, not on a throwaway copy.
    • The index signature { [key: string]: string[] } only tells the compiler what values to expect. At run time graph is an ordinary object, and keys like "*ot" are just property names.
    • Parentheses with in. !nextWord in minDist would negate the string first and then test whether false is a key, which is a different question (the compiler also rejects it). Wrap the test: !(nextWord in minDist).
    • Prototype keys. in also finds inherited properties, and "constructor" in {} is true. A word list that contains "constructor" would be mishandled by minDist and graph alike. A Map has no such issue; the next lesson on this problem uses one.
    • Scopes. The two loops each declare their own word, i and starWord. They are separate because each lives in its own block.

    Complexity

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

    Building the graph: O(N * L²). Each of the N words produces L patterns, and each pattern costs O(L) to build and hash.

    The search. Each word is queued at most once and, when expanded, looks at its L buckets. When buckets are small, this adds up to about O(N * L²) as well. In the worst case, many words share one pattern, and the buckets are large. Every word in a bucket of size k scans all k entries when it is expanded, so a single huge bucket costs up to O(N²) checks. Even then the work per check is a constant-time map lookup, which still beats comparing letters for every pair.

    Space: O(N * L²). The graph has up to N * L patterns, and each pattern is a string of length L. The buckets hold N * L references to the words.

    Edge cases and common mistakes

    • Start word not in the list. The start is queued directly and its patterns are looked up in graph, so it works. ladderLength("hit", "hot", ["hot"]) returns 2.
    • Target not in the list. It never appears in a bucket, never gets a distance, and the method returns 0.
    • The start word's own bucket. When the start is in the list, it is in its own buckets. It already has a distance, so the in check keeps it out of the queue.
    • Forgetting || []. The start word may produce a pattern that no list word shares, and for...of over undefined throws a TypeError.
    • Wrong substring bounds. word.substring(i + 1) skips the character at i. Using substring(i) would keep it and produce a pattern one character too long.
    • Distance 0 for the start. The lesson counts words, so the start has length 1.

    Testing

    • getStarWord("hot", 0) gives "*ot", getStarWord("hot", 1) gives "h*t" and getStarWord("hot", 2) gives "ho*".
    • "hit" to "cog" with ["hot","dot","dog","lot","log","cog"] gives 5.
    • The same words without "cog" give 0.
    • "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