Breadth first search

Breadth-first search(BFS) is an algorithm for searching a node in a tree which satisfies a given property. Normally, BFS will use a queue data structure to store node from each iteration.

Take the below image(from wiki) as an example.

If starting from root node 1, then follow the BFS, the steps are:

start from 1, init with a queue: [1]
pop from the queue, get node 1, queue: []
get node 1's neighbors, push them to the queue: [2,3,4]
pop from the queue, get node 2, queue: [3,4]
get node 2's neighbors, push them to the queue: [3,4,5,6]
pop from the queue, get node 3, queue: [4,5,6]
get node 3's neighbors, push them to the queue: [4,5,6]
pop from the queue, get node 4, queue: [5,6]
...
until queue is empty

Word Ladder

The Word Ladder problem asks that how many steps it takes to convert beginWord into endWord using a dictionary wordList. Each conversion should only change one single letter.

To tackle this problem, the first thing we need to figure out is how to make one conversion. Well, the answer is simple, we iterate every character and substitue it with every character from a-z, then we get all possible neighbors.

function getNeighbors(word: string): string[] {
    const neighbors: string[] = [];
    for (let i = 0; i < word.length; i++) {
        for (let j = "a".charCodeAt(0); j <= "z".charCodeAt(0); j++) {
            const chars = [...word];
            const c = String.fromCharCode(j);
            if (c === chars[i]) continue;
            chars[i] = c;
            neighbors.push(chars.join(""));
        }
    }
    return neighbors;
}

Then we check if the neighbor is in wordList. if it's true, then we get one valid conversion and push it to the queue, which is the standard BFS process.

function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
    const queue = [{ word: beginWord, level: 1 }];

    const a = "a".charCodeAt(0);
    const z = "z".charCodeAt(0);

    const words = new Set(wordList);

    while (queue.length > 0) {
        const { word, level } = queue.shift();
        if (word === endWord) return level;

        for (let i = 0; i < word.length; i++) {
            for (let j = a; j <= z; j++) {
                const char = String.fromCharCode(j);
                const chars = [...word];
                if (chars[i] === char) continue;
                chars[i] = char;
                const neighbor = chars.join("");

                if (words.has(neighbor)) {
                    // here we delete it from words, to avoid looping back
                    words.delete(neighbor);
                    queue.push({ word: neighbor, level: level + 1 });
                }
            }
        }
    }

    return 0;
};

Note above, we store the node with its level, so we know how many steps it should take.

Bidirectional Breadth First Search

Now we know how the BFS works. Let dig this problem deeper. From the above process, we saw that we start from the beginWord to endWord with BFS. How about start from endWord as well? If we make two queues, one starts from the beginWord, the other starts from the endWord. If there is a path between these two words, then they should meet in between. This process is called bidirectional BFS.

function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
    const words = new Set(wordList);
    if (!words.has(endWord)) return 0;

    const q1 = [beginWord];
    const visited1 = { [beginWord]: 1 };

    const q2 = [endWord];
    const visited2 = { [endWord]: 1 };

    const a = "a".charCodeAt(0);
    const z = "z".charCodeAt(0);

    while (q1.length > 0 && q2.length > 0) {
        let word: string | undefined;

        word = q1.shift();
        if (!word) return 0;

        if (word in visited2) {
            return visited1[word] + visited2[word] - 1;
        }
        for (let i = 0; i < word.length; i++) {
            for (let j = a; j <= z; j++) {
                const char = String.fromCharCode(j);
                const chars: string[] = [...word];
                if (chars[i] === char) continue;
                chars[i] = char;
                const neighbor = chars.join("");
                if (!words.has(neighbor)) continue;
                if (!(neighbor in visited1)) {
                    q1.push(neighbor);
                    visited1[neighbor] = visited1[word] + 1;
                }
            }
        }

        word = q2.shift();
        if (!word) return 0;
        if (word in visited1) {
            return visited1[word] + visited2[word] - 1;
        }
        for (let i = 0; i < word.length; i++) {
            for (let j = a; j <= z; j++) {
                const char = String.fromCharCode(j);
                const chars: string[] = [...word];
                if (chars[i] === char) continue;
                chars[i] = char;
                const neighbor = chars.join("");
                if (!words.has(neighbor)) continue;
                if (!(neighbor in visited2)) {
                    q2.push(neighbor);
                    visited2[neighbor] = visited2[word] + 1;
                }
            }
        }
    }

    return 0;
};

One thing needed to be noted: two variables visited is used here, to store all visited nodes of each. This is the key to check if these two BFS meet in between.