单词接龙（JS实现）

1 题目
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的*短转换序列的长度。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
输入:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出: 5
解释: 一个*短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
返回它的长度 5。
示例 2:
输入:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
输出: 0
解释: endWord “cog” 不在字典中，所以无法进行转换。

2 思路
这道题开始考察图的遍历，首先建立图结构，连接具有相同字母的单词，建立allWords，key为某种种形式，例如*ot，value为具有该形式的单词列表，例如hot、dot、lot，这样就可以快速得到指定形式的单词，随后从beginWord开始广度遍历整个图，当找到endWord时，表明得到了转换路径

3代码
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
var ladderLength = function(beginWord, endWord, wordList) {
if (!wordList.includes(endWord)) return 0;

let len = beginWord.length;
const allWords = {};

for (let word of wordList) { //遍历每个单词，建立图
for (let i=1; i<=len; i++) {
let key = `${word.slice(0,i-1)}*${word.slice(i,len)}`;
if (!allWords[key]) allWords[key] = [];
allWords[key].push(word);
}
}

const quque = [{word: beginWord, index: 1}]; //index用于记录走了多少步
const visited = {};

while(quque.length > 0) { //广度优先遍历整个图
let item = quque.shift();
for (let i=1; i<=len; i++) {
let key = `${item.word.slice(0,i-1)}*${item.word.slice(i,len)}`;
if (!allWords[key]) continue;
for (let j=0; j<allWords[key].length; j++) {
let word = allWords[key][j]
if (word === endWord) return item.index + 1;
if (visited[word]) continue;
quque.push({word, index: item.index + 1});
visited[word] = true;
}
}
}

return 0;
};