# yaox023's blog

·

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
``````

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.

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.