127. Word Ladder

1function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
2    const wordSet: Set<string> = new Set(wordList); // Space: O(n)
3    if (!wordSet.has(endWord)) {
4        return 0;
5    }
6
7    const queue: [string, number][] = [[beginWord, 1]] // [word, step]
8
9    while (queue.length > 0) { //O (wordList * n)
10        const [word, step] = queue.shift()!;
11        if (word === endWord) {
12            return step;
13        }
14
15        for (let i = 0; i < word.length; i++) {
16            for (let c = 'a'.charCodeAt(0); c <= 'z'.charCodeAt(0); c++) {
17                const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
18                if (wordSet.has(newWord)) {
19                    queue.push([newWord, step + 1])
20                    wordSet.delete(newWord);
21                }
22            } 
23        }
24    }
25
26    return 0;
27};

1function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
2    const word_set = new Set(wordList)
3    if (!word_set.has(endWord)) return 0;
4
5    let begin_set = new Set<string>([beginWord]);
6    let end_set = new Set<string>([endWord]);
7    let steps = 1;
8
9    while (begin_set.size > 0) {
10        steps++;
11        const next_set = new Set<string>();
12
13        begin_set.forEach(word => word_set.delete(word));
14
15        for (const word of begin_set) {
16            for (let i = 0; i < word.length; i++) {
17                for (let c = 'a'.charCodeAt(0); c <= 'z'.charCodeAt(0); c++) {
18                    const new_word = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
19
20                    if (end_set.has(new_word)) return steps;
21
22                    if (word_set.has(new_word)) {
23                        next_set.add(new_word);
24                        word_set.delete(new_word);
25                    }
26                }
27            }
28        }
29
30        begin_set = next_set;
31        if (begin_set.size > end_set.size) {
32            [begin_set, end_set] = [end_set, begin_set];
33        }
34    }
35    return 0;
36}