LeetCode题解：126. 单词接龙 II，BFS，JavaScript，详细注释

[chencl1986]

原题链接：126. 单词接龙 II

解题思路：

1. 可以使用BFS，在队列中直接存储变化的路径，例如[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]。
2. 每一层遍历都在wordList中搜索只变化了一次的单词，将其加入当前变化路径，同时做已访问的标记。
3. 当第一次遇到目标单词时，表示搜索完毕，将路径存入结果，退出循环。
4. 需要注意的用例：

"red"
"tax"
["ted","tex","red","tax","tad","den","rex","pee"]

/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {string[][]}
 */
var findLadders = function (beginWord, endWord, wordList) {
  // 将wordList存储为Set，方便快速判断新单词是否在wordList内
  let wordSet = new Set(wordList);

  // 如果目标单词不在wordList中，返回[]
  if (!wordSet.has(endWord)) {
    return [];
  }

  let result = []; // 存储最终结果
  let queue = [[beginWord]]; // 使用队列存储每次的遍历结果

  // 不断循环队列，清空时完成路径查找
  while (queue.length) {
    // 缓存当前层的路径数量
    let levelSize = queue.length;
    // 使用Set缓存当前层经过的单词，如果当前层有不止一个路径通过了同一个单词
    // 直接将其从wordSet中剔除，会减少查找到的路径
    // 对应用例："red"\n"tax"\n["ted","tex","red","tax","tad","den","rex","pee"]
    const levelSet = new Set();
    // 标识是否已找到最短路径
    let finished = false;

    // 将当前层的路径都清空，查找可以通往下一层的路径
    while (--levelSize >= 0) {
      // 出队一个路径，查找其下一个单词
      let path = queue.shift();
      // 当前需要变化的单词，在path的最后一位
      const word = path[path.length - 1];

      // 遍历word，生成所有可能的新单词
      for (let i = 0; i < word.length; i++) {
        // 在word的每一位，生成一个新的字母
        for (let j = 97; j < 123; j++) {
          // 使用ASCII码生成新字母
          const newChar = String.fromCharCode(j);

          // 如果新字母与当前word的字母相等，则跳过
          if (newChar === word[i]) {
            continue;
          }

          // 用新字母替换word[i]的字母，生成新单词
          const newWord = `${word.slice(0, i)}${newChar}${word.slice(i + 1)}`;

          // 如果新单词在wordSet中，才是下一个单词
          if (wordSet.has(newWord)) {
            // 如果新单词与目标相等，表示找到了转换路径
            if (newWord === endWord) {
              // 将path复制一份，同时将新的单词存入路径
              // 将转换路径存入结果
              result.push([...path, newWord]);
              // 当前层找到的所有路径，都是最短路径，将finished标识为true，结束查找
              finished = true;
            } else {
              // 将path复制一份，同时将新的单词存入路径
              // 将新路径存入队列，继续查找
              queue.push([...path, newWord]);
              // 将下一个变化的单词存入levelSet，它会在当前层遍历完成后，从wordSet中剔除
              // 能够避免下一层遍历中查找到同样单词，同时不会影响当前层后续的遍历
              levelSet.add(newWord);
            }
          }
        }
      }
    }

    // 如果finished为true，标识已经找到最短路径，退出循环，结束查找
    if (finished) {
      break;
    }

    // 将当前层使用过的单词从wordSet中剔除，避免重复查询
    for (const word of levelSet) {
      wordSet.delete(word);
    }
  }

  // 返回最终结果
  return result;
};

/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {string[][]}
 */
var findLadders = function (beginWord, endWord, wordList) {
  // 将wordList存储为Set，方便快速判断新单词是否在wordList内
  let wordSet = new Set(wordList);

  // 如果目标单词不在wordList中，返回[]
  if (!wordSet.has(endWord)) {
    return [];
  }

  let result = []; // 存储最终结果
  let queue = [[beginWord]]; // 使用队列存储每次的遍历结果

  // 不断循环队列，清空时完成路径查找
  while (queue.length) {
    // 缓存当前层的路径数量
    let levelSize = queue.length;
    // 使用Set缓存当前层经过的单词，如果当前层有不止一个路径通过了同一个单词
    // 直接将其从wordSet中剔除，会减少查找到的路径
    // 对应用例："red"\n"tax"\n["ted","tex","red","tax","tad","den","rex","pee"]
    const levelSet = new Set();
    // 标识是否已找到最短路径
    let found = false;

    // 将当前层的路径都清空，查找可以通往下一层的路径
    while (--levelSize >= 0) {
      // 出队一个路径，查找其下一个单词
      let path = queue.shift();
      // 当前需要变化的单词，在path的最后一位
      const word = path[path.length - 1];

      // 遍历wordSet中剩余的单词，查找下一个变化单词
      for (const newWord of wordSet) {
        // 统计新单词与当前单词的变化字母数量
        let diff = 0;

        // 遍历单词，统计变化字母数量
        for (let i = 0; i < newWord.length; i++) {
          if (word[i] !== newWord[i]) {
            // 统计变化数量
            diff++;

            // 变化数量大于1，肯定不是下一个变化单词，提前退出循环
            if (diff > 1) {
              break;
            }
          }
        }

        // 变化数量为1，表示找到了下一个变化单词
        if (diff === 1) {
          // 如果新单词与目标相等，表示找到了转换路径
          if (newWord === endWord) {
            // 将path复制一份，同时将新的单词存入路径
            // 将转换路径存入结果
            result.push([...path, newWord]);
            // 当前层找到的所有路径，都是最短路径，将finished标识为true，结束查找
            found = true;
          } else {
            // 将path复制一份，同时将新的单词存入路径
            // 将新路径存入队列，继续查找
            queue.push([...path, newWord]);
            // 将下一个变化的单词存入levelSet，它会在当前层遍历完成后，从wordSet中剔除
            // 能够避免下一层遍历中查找到同样单词，同时不会影响当前层后续的遍历
            levelSet.add(newWord);
          }
        }
      }
    }

    // 如果finished为true，标识已经找到最短路径，退出循环，结束查找
    if (found) {
      break;
    }

    // 将当前层使用过的单词从wordSet中剔除，避免重复查询
    for (const word of levelSet) {
      wordSet.delete(word);
    }
  }

  // 返回最终结果
  return result;
};