[127] 单词接龙

字典  wordList 中从单词 beginWord  和 endWord 的 转换序列 是一个按下述规格形成的序列  beginWord -> s1 -> s2 -> ... -> sk：

每一对相邻的单词只差一个字母。

对于  1 <= i <= k  时，每个  si  都在  wordList  中。注意， beginWord  不需要在  wordList  中。

sk == endWord

给你两个单词 beginWord  和 endWord 和一个字典 wordList ，返回 从  beginWord 到  endWord 的 最短转换序列中的 单词数目 。如果不存在这样的转换序列，返回 0 。

示例 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" 不在字典中，所以无法进行转换。

提示：

1 <= beginWord.length <= 10

endWord.length == beginWord.length

1 <= wordList.length <= 5000

wordList[i].length == beginWord.length

beginWord、endWord 和 wordList[i] 由小写英文字母组成

beginWord != endWord

wordList 中的所有字符串 互不相同

单向 BFS

这道题目作为一个 BFS 的典型题型，十分的有意思，解出来并不难，重点在于我们该怎么进行优化。

知道本题使用 BFS，那么 BFS 的核心就是队列，我们需要将每一层的节点都放入队列中，然后依次遍历，直到找到目标节点。

那么，对于每一层应该有哪些节点呢？其实，我们可以遍历当前的 wordList，然后将其中只差一个字母的单词都放入队列中，这样就可以得到下一层的节点。

判断两个字符串是否只差一个字母我们可以写一个函数判断。

const nextValidWords: string[] = [];
for (const nextWord of wordList) {
  let count = 0;
  for (let i = 0; i < curWord.length; i++) {
    if (curWord[i] !== nextWord[i]) {
      count += 1;
    }
    if (count > 1) break;
  }
  if (count === 1) nextValidWords.push(nextWord);
}

接下来，我们可以想想 BFS 的终止条件。由题目可知，当当前遍历的单词等于目标单词时，我们就可以返回当前的层数了。因此我们可以得到最终的解法。

function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  if (!wordList.includes(endWord)) return 0;

  const queue: string[] = [beginWord];
  const visited: string = [beginWord];
  let step = 1;

  while (queue.length > 0) {
    let len = queue.length;
    while (len--) {
      const curWord = queue.shift();
      if (curWord === endWord) return step;

      // 若已经访问过，则跳过
      if (visited.includes(curWord)) continue;

      const nextValidWords = findNextValidWords(curWord, wordList);
      for (const nextWord of nextValidWords) {
        // 将符合要求的单词放入队列中
        queue.push(nextWord);
        visited.push(nextWord);
      }
    }
    step += 1;
  }
  return 0;

  function findNextValidWords(curWord: string, wordList: Array<string>): string[] {
    const nextValidWords: string[] = [];
    for (const nextWord of wordList) {
      let count = 0;
      for (let i = 0; i < curWord.length; i++) {
        if (curWord[i] !== nextWord[i]) {
          count += 1;
        }
        if (count > 1) break;
      }
      if (count === 1) nextValidWords.push(nextWord);
    }

    return nextValidWords;
  }
}

优化方案

上面的方法虽然能够顺利 AC，但我们仍然可以想出更优秀的解决办法。

首先我们可以看到，我们在每一次选择中，都需要遍历整个 wordList 和 visited 数组，那么在大型的测试用例中显然运行时间会变长。首先我们可以想到，其实使用 Set 会更加的快速，因为 Set 的查找时间复杂度是 O(1)。我们仅需要维护一个 wordSet，并实时维护，则同样可以起到一样的效果。

再来我们可以注意 findNextValidWords 这个方法，对于每一次选择，我们都需要遍历整个 wordList，这样的时间复杂度实际上是 word.length * wordList.size。

我们可以换一个思路，因为单词是由 a~z 这有限数量的字符组成的，那么对于每一个单词，我们可以将其每一个字母都替换成 26 个字母，然后判断是否在 wordList 中，这样的时间复杂度就是 word.length * 26。在 wordList 较长的情况下仍然有常数级的性能。

因此我们可以根据优化思路，写出更新的解法：

function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  if (!wordList.includes(endWord)) return 0;

  const wordSet = new Set(wordList);
  const queue: string[] = [beginWord];
  let step = 1;

  while (queue.length > 0) {
    let len = queue.length;
    while (len--) {
      const curWord = queue.shift();
      if (curWord === endWord) return step;

      const nextValidWords = findNextValidWords(curWord, wordSet);
      for (const nextWord of nextValidWords) {
        queue.push(nextWord);
        // 从字典中删除，避免重复访问
        wordSet.delete(nextWord);
      }
    }
    step += 1;
  }
  return 0;

  function findNextValidWords(curWord: string, wordSet: Set<string>): string[] {
    const nextValidWords: string[] = [];

    // 单词集合比对遍历法，适合单词集合个数较少的情况，复杂度 word.length * wordSet.size
    // for (const nextWord of wordSet) {
    //   let count = 0;
    //   for (let i = 0; i < curWord.length; i++) {
    //     if (curWord[i] !== nextWord[i]) {
    //       count += 1;
    //     }
    //     if (count > 1) break;
    //   }
    //   if (count === 1) nextValidWords.push(nextWord);
    // }

    // 26个字母遍历法，适合单词集合个数较多的情况，复杂度 word.length * 26
    for (let i = 0; i < curWord.length; i++) {
      for (let j = 97; j <= 122; j++) {
        const nextWord = curWord.slice(0, i) + String.fromCharCode(j) + curWord.slice(i + 1);
        if (wordSet.has(nextWord)) {
          nextValidWords.push(nextWord);
          wordSet.delete(nextWord);
        }
      }
    }
    return nextValidWords;
  }
}

双向 BFS

双向 BFS 是一种优化 BFS 的方法，它的思路是从起点和终点同时开始搜索，当两边有交集的时候，就可以结束搜索。从而大大优化了搜索的时间复杂度。

在本题中，显然起点和重点都是十分明确的，因此我们可以使用双向 BFS 来优化搜索。

使用双向 BFS 的时候，我们需要维护两个队列，分别是从起点开始的队列和从终点开始的队列。我们每次都从两个队列中选择一个较小的方向进行 BFS，这样可以减少遍历次数。

终止条件有两个，当两个队列中有一个为空时，说明这条路一定不会有交集，因此可以直接返回 0。如果遍历过程中某一时刻，从一侧中遍历到的单词恰好已经被另一侧遍历过了，表明两个队列有交集，此时说明找到了最短路径，可以直接返回 step。

function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  if (!wordList.includes(endWord)) return 0;

  // 双向 BFS
  let queue1: string[] = [beginWord];
  let visited1 = new Set<string>();
  visited1.add(beginWord);
  let queue2: string[] = [endWord];
  let visited2 = new Set<string>();
  visited2.add(endWord);

  let step = 1;
  const wordSet = new Set<string>(wordList);

  while (queue1.length > 0 && queue2.length > 0) {
    // 永远选择更小的当前步骤选项集合进行 BFS，可以减少遍历次数
    if (queue1.length > queue2.length) {
      const tempQueue = queue1;
      queue1 = queue2;
      queue2 = tempQueue;
      const temp = visited1;
      visited1 = visited2;
      visited2 = temp;
    }

    let len = queue1.length;
    while (len--) {
      const curWord = queue1.shift();
      // 如果此时从一侧中遍历到的单词恰好已经被另一侧遍历过了，说明此时找到了最短路径
      if (visited2.has(curWord)) return step;

      const nextValidWords = findNextValidWords(curWord, wordSet);
      for (const nextWord of nextValidWords) {
        if (!visited1.has(nextWord)) {
          queue1.push(nextWord);
          visited1.add(nextWord);
        }
      }
    }
    step += 1;
  }
  return 0;

  function findNextValidWords(curWord: string, wordSet: Set<string>): string[] {
    const nextValidWords: string[] = [];
    // 26个字母遍历法，适合单词集合个数较多的情况，复杂度 word.length * 26
    for (let i = 0; i < curWord.length; i++) {
      for (let j = 97; j <= 122; j++) {
        const nextWord = curWord.slice(0, i) + String.fromCharCode(j) + curWord.slice(i + 1);
        if (wordSet.has(nextWord)) {
          nextValidWords.push(nextWord);
          wordSet.delete(nextWord);
        }
      }
    }

    return nextValidWords;
  }
}