题目

题解

已知条件：

相邻两个单词只会有单个字母不同邻里关系
必须从执行开始单词开始
结尾必须是指定的结束单词

邻里关系表

将邻里关系转换成图

分层示意图

第一步使用bfs建立图中的邻里关系，建立单词与层级之间的关系
第二步使用dfs + 回溯找出最短路径
代码

/**
 * 单词接龙II
 * @param {*} beginWord
 * @param {*} endWord
 * @param {*} wordList
 * 先构建图，将关系图构建出来
 */
var findLadders = function (beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  wordSet.add(beginWord);
  if (!wordSet.has(endWord)) {
    return [];
  }
  // 通过bfs将邻里关系与图制作出来
  // 单词与层级之间的关系
  const wordLevel = new Map();
  // 存放邻里关系 key：新单词，value: 父级单词
  const relationMap = new Map();
  // 访问过的单词列表
  const visitWordSet = new Set();
  // 单词队列
  const wordQueue = [beginWord];
    visitWordSet.add(beginWord);
  // 是否找到结束单词
  let isEnd = false;
  // 当前层级
  let level = 0;
  wordLevel.set(beginWord, 0);
  while (wordQueue.length) {
        const len = wordQueue.length;
    level++;
    // 遍历队列
    for (let i = 0; i < len; i++) {
      const word = wordQueue.shift();
      // 遍历单词的字母
      for (let l = 0; l < word.length; l++) {
        // 遍历26个字母
        for (let c = 97; c <= 122; c++) {
          // 生成新的单词
          const newWord =
            word.slice(0, l) + String.fromCharCode(c) + word.slice(l + 1);
          // 单词列表是否含有该单词
          if (!wordSet.has(newWord)) {
            continue;
          }
          // 单词关系列表是否含有
          if (relationMap.has(newWord)) {
            relationMap.get(newWord).push(word);
          } else {
            relationMap.set(newWord, [word]);
          }
          // 是否访问过
          if (visitWordSet.has(newWord)) {
            continue;
          }
          // 是否为结束单词
          if (newWord == endWord) {
            isEnd = true;
          }
          // 储存单词与层级关系
          wordLevel.set(newWord, level);
          // 将新单词添加进访问队列
          wordQueue.push(newWord);
          // 添加到访问列表
          visitWordSet.add(newWord);
        }
      }
    }
  }
  // 存放结果
  const result = [];
  /**
   * 深度优先搜索
   * @param {*} arr  初始数组
   * @param {*} word 当前单词
   * @param {*} endWord 结束单词
   * @returns
   */
  const dfs = (arr = [], word, endWord) => {
    // 递归出口
    if (endWord === word) {
      result.push([...arr, endWord]);
      return;
    }
    arr.push(word);
    //是否有邻里关系
    if (relationMap.has(word)) {
            // 获取邻里关系的数组
      const realationArr = relationMap.get(word);
            // 遍历邻里关系的数组
      for (let i = 0; i < realationArr.length; i++) {
                // 判断那个邻里关系的单词是当前单词的下一层
        if (wordLevel.get(word) + 1 === wordLevel.get(realationArr[i])) {
                    // 递归
          dfs(arr, realationArr[i], endWord);
        }
      }
    }
    arr.pop(); // 回溯
  };
  dfs([], beginWord, endWord);// dfs
    return result;
};

前端杂记

126. 单词接龙 II

题目

题解