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 frombeginWordtoendWord, or 0 if no such sequence exists.
Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.
Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
Pseudocode
- initially tried to solve it as a graph question
- still don't know understand solution
Solution
// No idea how this works lol
var ladderLength = function (begin, end, wordList) {
let set = new Set();
for (let val of wordList) {
if (val !== begin) set.add(val);
}
if (!set.has(end)) return 0;
let depth = 0;
let queue = [begin];
let size = queue.length;
let a = "a".charCodeAt(0);
while (queue.length > 0) {
depth++;
while (size > 0) {
let str = queue.shift();
for (let i = 0; i < str.length; i++) {
for (let j = 0; j < 26; j++) {
let search =
str.slice(0, i) + String.fromCharCode(a + j) + str.slice(i + 1);
if (search === str) continue;
if (search === end) return depth + 1;
if (set.has(search)) {
queue.push(search);
set.delete(search);
}
}
}
size--;
}
size = queue.length;
}
return 0;
};
//hit
