Word Ladder
Given two words (beginWord and endWord), and a dictionary's word list, find the length of the shortest transformation sequence from beginWord to endWord, such that: 1) Only one letter can be changed at a time. 2) Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Constraints:
- 1 <= beginWord.length <= 10
- endWord.length == beginWord.length
- 1 <= wordList.length <= 5000
- wordList[i].length == beginWord.length
- beginWord, endWord, and wordList[i] consist of lowercase English letters.
- beginWord is not the same as endWord.
- All the words in wordList are unique.
Examples:
Input: ["hit","cog","dot","dog","lot","log","cog"], "hit", "cog"
Output: 5
Explanation: One possible transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", and another possible transformation is "hit" -> "hot" -> "lot" -> "log" -> "cog".
Solutions
Breadth-First Search
The solution uses a breadth-first search (BFS) approach to find the shortest transformation sequence. It starts with the beginWord and explores all possible transformations by changing one letter at a time. The transformed words are added to a queue and the process continues until the endWord is found or the queue is empty.
function ladderLength(beginWord, endWord, wordList) {
let wordSet = new Set(wordList);
let queue = [[beginWord, 1]];
while (queue.length) {
let [word, length] = queue.shift();
if (word === endWord) return length;
for (let i = 0; i < word.length; i++) {
for (let j = 0; j < 26; j++) {
let nextWord =
word.slice(0, i) + String.fromCharCode(97 + j) + word.slice(i + 1);
if (wordSet.has(nextWord)) {
queue.push([nextWord, length + 1]);
wordSet.delete(nextWord);
}
}
}
}
return 0;
}
Follow-up:
What if the word list is very large and we need to optimize the solution for memory usage?
