LeetCode 244. 最短单词距离 II

2024-06-24 HGNULB 约 9 分钟

文章信息 7 个分类 5 个标签

分类

题目描述

✅ 244. 最短单词距离 II

题意分析

这是一道设计题：构造函数拿到一个字符串数组，之后会被反复调用 shortest(word1, word2)，每次返回这两个单词在数组中出现位置的最小下标差。题目保证两个单词都存在于数组中且互不相同。

题面里「会被多次调用」这句话是最强的信号：它意味着评价标准不是单次查询有多快，而是「一次预处理 + 多次查询」的总代价。凡是出现这种表述，正确的反应就是把可以离线算好的东西挪到构造函数里，让查询只做最小必要的工作。

数组长度可达 3×10^4，查询次数同样可达 5×10^3。如果每次查询都重扫整个数组，总代价是这两者相乘，达到 1.5×10^8 级别；而如果查询只碰这两个词自己的出现位置，绝大多数查询会短得多。

边界包括：某个单词在数组中只出现一次；两个单词的出现位置完全交错；两个单词的出现次数极度不均衡（一个出现上万次，另一个只出现一次）。题目保证 word1 != word2，所以不必处理同词自比的情况。

解法：预处理位置表

核心思路

暴力做法是每次查询都从头扫一遍数组，一边扫一边记录最近一次见到 word1 的位置和最近一次见到 word2 的位置，每次更新时用两者之差刷新答案。单次是 $O(n)$，但查询有几千次，总代价是 $O(nq)$，瓶颈在于每次查询都要把与本次问题无关的成千上万个单词重新读一遍。

观察点在于：一次查询真正用到的信息，只是 word1 和 word2 各自出现在哪些下标上，其余单词完全是噪声。而这份「单词到下标列表」的映射与查询参数无关，可以在构造时一次性算好，之后被所有查询共享。

更进一步的观察是，按数组顺序收集下标时，每个单词的下标列表天然是严格递增的。两个有序列表求最小差值，正是归并式双指针的经典形态：始终推进当前值较小的那个指针，因为落后的那一侧才有可能通过前进缩小差距，而领先的一侧继续前进只会让差值更大。

由此得到查询过程的不变量：在双指针推进的任意时刻，所有下标对 (a[x], b[y]) 中满足 x < i 或 y < j 的那些，其最小差值已经被 best 记录过。换句话说，被跳过的配对都是可证明的非最优解，因此扫完两条列表后 best 就是全局最小值。

支撑这条不变量的引理是：若当前 a[i] < b[j]，那么对任意 y >= j 都有 b[y] >= b[j] > a[i]，于是 b[y] - a[i] >= b[j] - a[i]，说明 a[i] 与 b 中后续所有元素的配对都不可能优于当前刚算过的这一对，a[i] 可以安全退休。

解题步骤

在构造函数里遍历一次数组，把每个单词映射到它出现的下标列表上。之所以放在构造函数而不是查询里，是因为这份映射与查询参数无关，摊到多次查询上，预处理成本被完全稀释。

收集下标时按数组的自然顺序追加。之所以不需要额外排序，是因为遍历本身就是按下标递增的，追加得到的列表天然有序，这一点是后续双指针成立的前提。

查询时先取出两个单词各自的下标列表 a 和 b。之所以可以不判空，是因为题目保证两个词都在数组中出现过，列表必然非空。

初始化双指针 i = j = 0 和答案 best 为一个足够大的值。之所以初值取极大，是因为答案是取最小值的过程，任何真实差值都必须能把它压下去。

循环条件是两个指针都未越界。之所以是「与」而不是「或」，是因为任何一条列表走完后，剩下那条的元素都只会离对方越来越远，继续比较不可能产生更小的差值。

每轮先用 abs(a[i] - b[j]) 更新 best，再推进值较小的那个指针。之所以必须先更新后推进，是因为当前这一对正是「较小值所能达到的最优配对」，一旦先推进就永远错过了它。

推进规则是 a[i] < b[j] 时动 i，否则动 j。之所以不能两个一起动，是因为那会跳过潜在的最优配对；之所以相等时动谁都行，是因为题目保证两词不同，同一下标不会同时属于两条列表，a[i] == b[j] 实际不会发生。

循环结束后返回 best。

以 wordsDict = ["practice", "makes", "perfect", "coding", "makes"] 走一遍。构造后位置表是 practice -> [0]，makes -> [1, 4]，perfect -> [2]，coding -> [3]。

查询 shortest("coding", "practice")：a = [3]，b = [0]，i = j = 0，best = |3 - 0| = 3；a[0] = 3 不小于 b[0] = 0，推进 j 到 1，越界，循环结束，返回 3。

查询 shortest("makes", "coding")：a = [1, 4]，b = [3]。第一轮 best = |1 - 3| = 2；a[0] = 1 < b[0] = 3，推进 i 到 1。第二轮 best = min(2, |4 - 3|) = 1；a[1] = 4 不小于 3，推进 j 到 1 越界，循环结束，返回 1。注意如果第一轮推进的是 j，就会直接跳出循环并错误返回 2，这正说明「推进较小值」这条规则的必要性。

代码实现

class WordDistance {
    private final Map<String, List<Integer>> pos = new HashMap<>();

    public WordDistance(String[] wordsDict) {
        for (int i = 0; i < wordsDict.length; i++) {
            pos.computeIfAbsent(wordsDict[i], k -> new ArrayList<>()).add(i);
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> a = pos.get(word1);
        List<Integer> b = pos.get(word2);
        int i = 0;
        int j = 0;
        int best = Integer.MAX_VALUE;

        while (i < a.size() && j < b.size()) {
            best = Math.min(best, Math.abs(a.get(i) - b.get(j)));
            if (a.get(i) < b.get(j)) {
                i++;
            } else {
                j++;
            }
        }

        return best;
    }
}

type WordDistance struct {
    pos map[string][]int
}

func Constructor(wordsDict []string) WordDistance {
    pos := make(map[string][]int)
    for i, w := range wordsDict {
        pos[w] = append(pos[w], i)
    }
    return WordDistance{pos: pos}
}

func (w *WordDistance) Shortest(word1 string, word2 string) int {
    a := w.pos[word1]
    b := w.pos[word2]
    i, j := 0, 0
    best := 1 << 30

    for i < len(a) && j < len(b) {
        d := a[i] - b[j]
        if d < 0 {
            d = -d
        }
        if d < best {
            best = d
        }

        if a[i] < b[j] {
            i++
        } else {
            j++
        }
    }

    return best
}

复杂度分析

时间复杂度：构造为 $O(n)$，凭据是只对数组做一次遍历，每个下标做一次哈希查找加一次列表追加；单次查询为 $O(p + q)$，其中 $p$、$q$ 分别是两个单词的出现次数，凭据是每轮循环至少推进一个指针一步，两个指针合计最多走 $p + q$ 步，且所有 $p + q$ 的上界都是 $n$。

空间复杂度：$O(n)$，凭据是位置表中所有列表的元素总数恰好等于数组长度，每个下标只被存一次；查询过程本身只用了两个指针和一个答案变量，是常数额外空间。

关键点总结

看到「同一份数据被多次查询」就要立刻把工作量往构造函数搬，用一次线性预处理换掉每次查询的线性扫描，这是所有设计类题目的第一反应。

按遍历顺序收集下标能天然得到有序列表，省掉一次排序。凡是「记录出现位置」的场景都可以吃到这个红利，不要习惯性补一次 sort。

两个有序序列求最小差值的标准解法是归并式双指针，核心论证是「推进较小值」的支配关系：领先方继续前进只会让差距更大，所以落后方才是唯一有改进空间的一侧。

循环里必须先结算当前配对再移动指针，顺序颠倒会漏掉恰好是最优解的那一对，这在所有双指针求极值的题里都是同一个坑。

面试视角：面试官通常会先让你写出单次 $O(n)$ 的扫描版（也就是本题的第一问），然后加上「会被调用很多次」这句话看你会不会主动改设计。答题时要显式说出「预处理成本被多次查询摊薄」这层权衡，并能回答追问「如果两个词出现次数悬殊，能否更快」——此时可以提出在长列表上对短列表的每个下标做二分，把单次查询降到 $O(\min(p,q) \log \max(p,q))$。

易错点总结

每次查询都重新遍历原数组：用例数组长 3×10^4、查询 5×10^3 次，总操作量 1.5×10^8，在多次调用的判题下超时，而预处理版只碰两个词自己的下标。

循环里先推进指针再计算差值：用例 a = [1, 4]、b = [3]，第一轮直接推进 i 而不结算，|1 - 3| = 2 被跳过；若最优解恰好在首对上（如 a = [0]、b = [1]），会返回初始极大值。

推进规则写反成「推进较大值的指针」：用例 a = [1, 4]、b = [3]，第一轮推进 j 到越界，循环立即结束，返回 2，而正确答案是 1。

循环条件写成 i < a.size() || j < b.size()：用例 a = [3]、b = [0]，j 推到 1 后仍进入循环体，访问 b.get(1) 抛出下标越界异常。

每轮同时推进两个指针：用例 a = [0, 5]、b = [4]，第一轮算出 4 后 i 和 j 一起走，j 越界退出，漏掉 |5 - 4| = 1，返回 4 而非 1。

用 int 相减求绝对值时不做 Math.abs，直接写 b.get(j) - a.get(i)：用例 a = [5]、b = [0]，得到 -5，Math.min 之后 best 变成负数，返回 -5。

在构造函数里用 pos.put(word, list) 而不是 computeIfAbsent，每次遇到同一个词都新建列表：用例 ["makes", "coding", "makes"]，makes 的列表被覆盖成只剩 [2]，查询 shortest("makes", "coding") 返回 1，而正确答案是 1 恰好蒙对，但换成 ["makes", "a", "b", "coding"] 加上后续重复就会直接丢失更近的那次出现。

预处理时存的是「最近一次出现的下标」这一个整数而不是完整列表：用例 ["a", "b", "a"] 查询 shortest("a", "b")，只记住 a -> 2，算出 1，看似正确，但 ["a", "x", "x", "b", "a"] 只记住 a -> 4 会给出 1，而真正的最短是 |4 - 3| = 1，一旦查询顺序或数据换成 ["a", "b", "x", "x", "a"] 就会错过 |0 - 1| = 1。

Go 里把 best 初始化为 0：用例任意输入，d < best 永远不成立，函数恒返回 0。

Go 里对 w.pos[word1] 取值后未意识到不存在时返回的是 nil 切片：若题目不保证单词存在，len(nil) == 0 会让循环一次都不执行，返回哨兵值 1 << 30 而不是报错，需要按题意决定是否显式处理。

相似题目

题目	难度	考察点
88. 合并两个有序数组	简单	同样是两条有序序列的归并推进，但要原地从后往前写以避免覆盖
350. 两个数组的交集 II	简单	双指针目标从求最小差值变为收集相等元素，需处理重复计数
349. 两个数组的交集	简单	结果要求去重，推进时需跳过与上一个相同的元素
986. 区间列表的交集	中等	元素从单点升级为区间，推进依据变成右端点谁先结束
21. 合并两个有序链表	简单	同一套归并逻辑落在链表上，考察指针接续与哨兵头节点