Published Mar 25, 2022
[
A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:
si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.sk == endWordGiven 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.
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.
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.
- `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 != endWord`
- All the words in `wordList` are **unique**.
function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
// use Set for existence check & unique
const words = new Set(wordList);
// we can delete begin word since it doesn't need be to in the wordList
words.delete(beginWord);
// nice to have an object queue
const q = [{ word: beginWord, distance: 1 }];
// BFS starts here
while (q.length) {
// destructure the values & check
const { word, distance } = q.shift();
if (word === endWord) return distance;
// find word with one char difference from the original word
// and update the distance.
for (let i = 0; i < word.length; i++) {
for (let j = 0; j < 26; j++) {
const char = String.fromCharCode('a'.charCodeAt(0) + j);
const mod = word.slice(0, i) + char + word.slice(i + 1);
if (words.delete(mod)) q.push({ word: mod, distance: distance + 1 });
}
}
}
return 0;
};