LeetCode 244. 最短单词距离 II

2024-06-24 HGNULB 约 4 分钟

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

分类

LeetCode CodeTop 中等未解决会员题 2-5 字节阿里

题目描述

✅ 244. 最短单词距离 II

题意分析

同一词数组需要多次查询两个不同且已存在单词的最短下标距离。先存位置列表，查询只读相关两个词。

解法：预处理位置表

核心思路

[!blue]

同一数组会被查询多次，先建立 单词 → 全部出现下标 的哈希表，之后每次只读取被查询的两个单词。构造时从左到右追加下标，每个位置列表天然递增；必须保存全部位置，因为最近的一对可能出现在数组中间，不能只保留第一次或最后一次。

设两张位置表为 a、b，用 i、j 指向各自尚未处理的第一个位置。先以 abs(a[i]-b[j]) 更新最小距离，再推进位置较小的一侧：若 a[i] < b[j]，b 的后续位置都不小于 b[j]，它们与固定的 a[i] 只会更远，所以 a[i] 已没有继续保留的价值；反过来则淘汰 b[j]。

每次跳过的后续配对都不可能优于刚刚比较的这一对，此前淘汰的位置也按同样理由处理过，因此不会漏掉更优答案。任一列表走完时，其所有位置都已安全淘汰，另一侧剩余位置也不能改进结果，可以结束查询。

题目保证两个查询单词不同且都存在，所以两张列表都非空，同一个下标不会同时属于两边。最小距离从一个足够大的数开始，不能初始化为 0，因为合法距离都是正数。

解题步骤

构造时按词收集全部位置。

查询取两个有序列表。

计算当前绝对差并更新最小值，再前进较小一侧。

任一列表耗尽后返回。

代码实现

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(S)$，S 为词数组总字符数；单次查询 $O(p+q)$，p、q 为两个词的出现次数，另有查询词哈希成本。

空间复杂度：$O(n)$，n 为单词数组长度，所有位置表总共保存 n 个下标，单词键引用输入；单次查询只使用常数个游标。

关键点总结

[!green]

必须保存全部位置，单独最后一次不足以回答任意两词距离。

收集顺序已经有序，无需再排序。

易错点总结

[!yellow]

同时推进两侧会跳过更近配对。

只记最后位置会丢掉此前出现的更近配对，无法支持任意两个单词的查询。

以零初始化最小值，后续正距离无法更新。

相似题目

题目	难度	关联与区别
面试题 17.11. 单词距离	中等	只查一次时可线性扫描并保留最近位置；本题重复查询，预处理词到位置列表更合适。
243. 最短单词距离	简单	同系列。I 为单次查询扫描两单词的最近下标；II 面向多次查询，预存位置列表后用双指针求距离。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2024/34094117

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！