Word Ladder
A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:
Every adjacent pair of words differs by a single letter.
Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.
var ladderLength = function(beginWord, endWord, wordList) {
const wordSet = new Set(wordList)
let queue = [beginWord];
let steps = 1;
while(queue.length) {
const next = [];
// loop over each word in the queue
for(let word of queue) {
if(word === endWord) return steps;
// loop over each char of the word
for(let i = 0; i < word.length; i++) {
// and replace the char with letters from [a - z]
for(let j = 0; j < 26; j++) {
const newWord = word.slice(0, i) + String.fromCharCode(j + 97) + word.slice(i+1);
// if the new word exist in the word list add it to the queue
if(wordSet.has(newWord)) {
next.push(newWord);
wordSet.delete(newWord);
}
}
}
}
queue = next
steps++;
}
return 0;
};Posted by Jamie Meyer 19 days ago