LeetCode 244. 最短单词距离 II

Categories:

题目描述
思路分析
1. 解法一：预处理位置表（推荐）
相似题目

题目描述

✅ 244. 最短单词距离 II

思路分析

解法一：预处理位置表（推荐）

核心思路：

预处理每个单词在数组中的出现位置列表。

每次查询使用双指针在两列表中求最小距离。

多次查询可复用预处理结果。

复杂度分析：

时间复杂度：预处理 O(n)，单次查询 O(a+b)。

空间复杂度：O(n)。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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
}

相似题目

题目	难度	考察点
244. 最短单词距离 II	中等	预处理
243. 最短单词距离	简单	扫描
245. 最短单词距离 III	中等	扫描
76. 最小覆盖子串	困难	滑动窗口
159. 至多包含两个不同字符的最长子串	中等	滑动窗口

本文作者: HGNULB

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