Sponsored
Sponsored
This approach leverages Breadth First Search (BFS), where each word is a node in the graph, and an edge exists between two nodes if they differ by exactly one letter. The goal is to find the shortest path from beginWord to endWord.
Start BFS from the beginWord, exploring transformations by changing each letter and checking if the new word exists in the set of available words. Polished implementation should consider preprocessing the word list for efficient lookup.
Time Complexity: O(N * m^2), where N is the number of words in the list and m is the length of each word. Each word pair is compared in the worst case.
Space Complexity: O(N), where N is the number of nodes (words) we store in the queue.
1const ladderLength = function(beginWord, endWord, wordList) {
2 const wordSet = new Set(wordList);
3 if (!wordSet.has(endWord)) return 0;
4 let queue = [beginWord];
5 let ladder = 1;
6
7 while (queue.length > 0) {
8 const levelSize = queue.length;
9 for (let i = 0; i < levelSize; i++) {
10 const current = queue.shift();
11 for (let j = 0; j < current.length; j++) {
12 for (let c = 97; c <= 122; c++) {
13 const nextWord = current.substring(0, j) + String.fromCharCode(c) + current.substring(j + 1);
14 if (nextWord === endWord) return ladder + 1;
15 if (wordSet.has(nextWord)) {
16 wordSet.delete(nextWord);
17 queue.push(nextWord);
18 }
19 }
20 }
21 }
22 ladder++;
23 }
24 return 0;
25};
26
27const beginWord = "hit";
28const endWord = "cog";
29const wordList = ["hot", "dot", "dog", "lot", "log", "cog"];
30
31console.log(ladderLength(beginWord, endWord, wordList));This JavaScript solution employs BFS to traverse transformations, exploring words that differ by a single letter. Each step pushes eligible words to the queue and removes them from the valid set for space optimization. The ladder depth increments with each level of breadth explored.