127. Word Ladder
Tags:
Hard
Skills:
BFS
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Tìm số bước biến đổi ngắn nhất từ beginWord → endWord, mỗi bước chỉ thay đổi 1 ký tự, các từ trung gian phải có trong wordList
Approach
Solution - Traditional BFS
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};Solution - Bidirectional BFS
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}