Problem
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
- Only one letter can be changed at a time.
- Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
- You may assume no duplicates in the word list.
- You may assume beginWord and endWord are non-empty and are not the same.
Example 1:
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Example 2:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
Solution
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
var ladderLength = function(beginWord, endWord, wordList) {
var wordSet = new Set(wordList);
var queue = [];
var step = 0;
var word = '';
var len = 0;
var i = 0;
pushNextWord(beginWord, queue, wordSet);
step = 2;
while (len = queue.length) {
for (i = 0; i < len; i++) {
word = queue.shift();
if (word === endWord) return step;
pushNextWord(word, queue, wordSet);
}
step++;
}
return 0;
};
var pushNextWord = function (word, queue, wordSet) {
var start = 'a'.charCodeAt(0);
var len = word.length;
var str = '';
wordSet.delete(word);
for (var i = 0; i < len; i++) {
for (var j = 0; j < 26; j++) {
str = word.substr(0, i) + String.fromCharCode(j + start) + word.substr(i + 1);
if (wordSet.has(str)) {
queue.push(str);
wordSet.delete(str);
}
}
}
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).