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

"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;};