[JavaScript 刷题] 搜索 - 最短单词路径, leetcode 127

github repo 地址: https://github.com/GoldenaArcher/js_leetcode，Github 的目录 大概 会更新的更勤快一些。

刷了两道 BFS 这道题解起来其实就挺轻松的了，题目地址：127. Word Ladder

题目如下：

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

• Every adjacent pair of words differs by a single letter.
• Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
• sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the *number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists*.

解题思路

刷了两天的 BFS 了，一看到这个题型，第一反应先画个图，然后直接用 BFS 解……

图如下：

本质上还是用 BFS 去解题就是了，将下一层的结点推到 queue 里面，如果在循环体内找到了 endWord，那么直接返回找到的数字。

如果在循环体外，那么就证明没有找到 endWord，按照题目返回 0 即可。

使用 JavaScript 解题

这里写了一个 util 函数，用来判断两个单词是否相近，虽然题目中出现了 unique 这个关键字，但是最后判断还是用了 diff === 1;。

const isAdjacentWord = (w1, w2) => {
  let diff = 0;
  for (let i = 0; i < w1.length; i++) {
    if (w1[i] !== w2[i]) diff++;
    if (diff > 1) return false;
  }

  return diff === 1;
};

/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function (beginWord, endWord, wordList) {
  if (!wordList || !beginWord || !endWord) return 0;

  const queue = [[beginWord, 1]];
  const usedWords = new Set();

  while (queue.length > 0) {
    const [currWord, numOfTransformation] = queue.shift();
    if (currWord === endWord) return numOfTransformation;
    for (const word of wordList) {
      if (usedWords.has(word)) continue;

      if (isAdjacentWord(word, currWord)) {
        queue.push([word, numOfTransformation + 1]);
        usedWords.add(word);
      }
    }
  }

  return 0;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

优化

这里有两个优化是可以做的。

bidirectional BFS

这个跑的就不是很快，我找了一下资料，有一个优化是叫 bidirectional BFS，原理大概是下面这样的：

即从 beginWord 和 endWord 两边一起开始搜索，这张图上看不出来怎么节省时间的，所以我又画了一张图：

蓝色圈起来的是从 beginWord 向下搜索的部分，红色圈起来的是从 endWord 网上搜索的部分，黄色高亮的则是 bidirectional BFS 搜索时经历的结点，比起最基础的 BFS 来说可以提速很多。

bidirectional BFS 就……之后再说吧，写了一段时间总是卡，我估计这几天死磕也想不出来为什么了，再刷点题找点感觉再回来解。

面试情况下知道有这个解法，问一下面试官应该说可以根据对方的 hint 解题了。

使用 pattern

这里就是一个个单词去进行比较了，另外一种方式是使用 pattern 去进行比较。

我看到有一个 python 解法就是将所有的 words 加到 pattern 中进行对比，速度大概是超过同期 90%，然后空间超过同期 20%，所以大概也是个空间换时间的做法。

大概意思就是将所有可能的组合放置到一个新的字典中，以 abc 为例，会有下面三种组合：

const dict = new Set(["ab*", "a*c", "*bc"]);
1

随后每次便利的时候进行 match，具体实现是怎么做的还是得研究下，在不使用 bidirectional BFS 的情况下这样也能够提速。