LeetCode题解：127. 单词接龙，BFS+生成所有可能新单词再匹配，JavaScript，详细注释

[chencl1986]

原题链接：127. 单词接龙

解题思路：

1. 使用队列进行BFS，队列中的每个元素都存储当前层的字符串与当前转换长度。
2. 将wordList保存为Set，用于查找每一层转换的单词，如果找到就从Set中删除，以减少遍历次数。
3. 每次循环都出队一个元素，同时生成当前单词所有可能被替换的情况，以单词hit为例，新生成的单词为it、ht、hi*，*号可被a-z替代。
4. 将所有可能的新单词在wordList中，表示该单词为下一层的元素，即可把该单词入队，同时转换长度加一。
5. 如果新单词与endWord相等，表示找到了最短转换序列，返回当前长度即可。
6. 需要注意的测试用例：

"ymain"
"oecij"
["ymann","yycrj","oecij","ymcnj","yzcrj","yycij","xecij","yecij","ymanj","yzcnj","ymain"]

/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function (beginWord, endWord, wordList) {
  // 将起始词存入队列，开始搜索
  // 队列中的每个元素都保存了当前单词，以及当前元素所在的层次
  let queue = [[beginWord, 1]];
  let wordSet = new Set(wordList); // 将wordList保存为Set，用于遍历

  // 遍历队列，直到队列中元素全部出队，即为完成搜索
  while (queue.length) {
    // 将队列中的元素出队
    let [str, count] = queue.shift();

    // 遍历当前单词的每个字符
    for (let i = 0; i < str.length; i++) {
      // 生成a-z的字符
      for (let j = 97; j < 123; j++) {
        // 以单词hit为例，此处生成的是该单词中每个字母所有可能变化情况
        // 即为*it、h*t、hi*，*号可被a-z替代
        const newWord =
          str.slice(0, i) + String.fromCharCode(j) + str.slice(i + 1);

        // 判断新生成的单词是否在Set中
        if (wordSet.has(newWord)) {
          // 如果新生成的单词与目标相同，表示找到了最小路径，返回当前转换长度
          if (newWord === endWord) {
            return count + 1;
          }
          // 将新单词存入队列，并将转换长度加一，表示进入了下一层遍历
          queue.push([newWord, count + 1]);
          // 在Set中删除已遍历过的单词，避免重复遍历
          wordSet.delete(newWord);
        }
      }
    }
  }

  // 如果退出循环，表示未找到路径，返回长度为0
  return 0;
};