LeetCode 面试题 17.11. 单词距离
题目描述
题意分析
在单词数组中，求两个不同目标词
word1、word2出现位置的最小下标距离。两个词都在数组中出现过，相邻位置的距离为 1，不需要再减 1。单次查询只需扫描数组；题面还要求考虑同一文本上的多次不同查询，这时可以预处理各词位置，避免每次重新扫描全文。
解法：维护两个最近位置
核心思路
[!blue]
用
last1、last2分别记录扫描前缀中两个目标词最近一次出现的下标，初始为 -1，表示尚未遇到。遇到某个目标词时更新对应下标，两者都有效后，用它们的绝对差更新最小距离。对当前新出现的位置
i，另一个词的历史下标都在它左边，其中最大的下标离i最近。更早位置只会产生更大距离，因此只保留另一个词最近的位置就足够。任意合法词对都会在较晚的那个位置被读到时接受比较：如果较早位置已经被同类词的新位置替代，替代后的距离只会更小。所以丢弃旧位置不会漏掉最优答案。处理完每个下标后，
answer始终是已扫描前缀中的最短距离。
解题步骤
- 两个最近下标初始化为 -1，答案初始化为数组长度，这是合法下标距离的上界。
- 从左到右扫描，命中
word1就更新last1，否则若命中word2则更新last2。- 两个下标都有效时，用
abs(last1 - last2)更新答案。- 扫描完成后返回答案。题目保证两个词都出现，所以最终一定存在有效距离。
代码实现
class Solution {
public int findClosest(String[] words, String word1, String word2) {
int last1 = -1;
int last2 = -1;
int answer = words.length;
for (int i = 0; i < words.length; i++) {
if (words[i].equals(word1)) {
last1 = i;
} else if (words[i].equals(word2)) {
last2 = i;
}
if (last1 != -1 && last2 != -1) {
answer = Math.min(answer, Math.abs(last1 - last2));
}
}
return answer;
}
}
func findClosest(words []string, word1 string, word2 string) int {
last1, last2 := -1, -1
answer := len(words)
for i, word := range words {
if word == word1 {
last1 = i
} else if word == word2 {
last2 = i
}
if last1 != -1 && last2 != -1 {
distance := last1 - last2
if distance < 0 {
distance = -distance
}
answer = min(answer, distance)
}
}
return answer
}
复杂度分析
- 时间复杂度：按单词比较为常数计算时是 $O(n)$；计入字符串比较，若数组总字符数为
S，上界为 $O(S+n)$。- 空间复杂度：$O(1)$。只保存两个最近下标和答案。
关键点总结
[!green]
- 对固定的新位置，另一个词的最近历史位置就是最优选择。
- 每个最优词对都会在较晚位置出现时被考虑，或被距离更小的词对替代。
- -1 只表示尚未出现，必须等两边都有效后再计算距离。
进阶：预处理位置表 + 双指针
核心思路
[!blue]
同一个文本要查询多次时，构造
WordDistance对象，将每个单词映射到它的全部出现下标。按原数组顺序追加，这些列表天然递增，不需要另行排序。索引只构建一次，之后在同一对象上反复调用shortest/Shortest。一次查询只取两个目标词的位置表
a、b，用i、j指向当前下标。先比较abs(a[i] - b[j])，再前进数值较小的一侧。若a[i] < b[j]，b的后续下标只会更大，与固定a[i]的距离不会缩小，所以可以安全丢弃a[i]；另一侧同理。每次淘汰的下标与对面后续位置都不会产生更优答案，更早的对面位置也已经按同样规则处理过，因此不会漏掉最近的一对。任一列表耗尽就结束；查询只移动局部游标，不修改位置表，可以继续用于下一次查询。
解题步骤
- 构造时顺序扫描一次文本，把每个下标追加到所属单词的位置列表。
- 查询时读取两个有序列表，初始化两个游标和足够大的最小距离。
- 比较当前位置的绝对差，更新答案，再推进下标较小的一侧。
- 一侧用尽后返回最小值。沿用原题前提：查询词不同，且都存在于文本中。
代码实现
class WordDistance {
private final Map<String, List<Integer>> pos = new HashMap<>();
public WordDistance(String[] words) {
for (int i = 0; i < words.length; i++) {
pos.computeIfAbsent(words[i], key -> 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(words []string) WordDistance {
pos := make(map[string][]int)
for i, word := range words {
pos[word] = append(pos[word], 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) {
distance := a[i] - b[j]
if distance < 0 {
distance = -distance
}
if distance < best {
best = distance
}
if a[i] < b[j] {
i++
} else {
j++
}
}
return best
}
复杂度分析
- 时间复杂度：构造期望 $O(S+n)$，
S为文本总字符数，包含哈希成本。单次双指针查询为 $O(p+q)$，p、q是两个词的出现次数，另有查询词本身的哈希成本。- 空间复杂度：索引占 $O(n)$，所有位置表一共保存
n个下标；单次查询只需要 $O(1)$ 辅助空间。
关键点总结
[!green]
- 重复查询复用同一份位置表，不应在每次查询时重新构造对象。
- 必须保存全部位置，最短距离不一定发生在两个词最后出现的地方。
- 较小下标与对面后续下标只会更远，所以每轮淘汰较小一侧。
易错点总结
[!yellow]
- Java 字符串应使用
equals比较内容，不能用==比较对象是否相同。- 单次扫描的未出现标记不能参与距离计算，也不能只记录每个词首次出现的位置。
- 位置差需要取绝对值，不能让负数错误成为最小距离。
- 多次查询时只保存每个词最后位置，会丢失文本前面更近的配对。
- 两条位置表不能无条件同时推进，否则可能跳过更近的组合。
- 查询游标应是本次调用的局部状态，不能消耗或修改后续查询还要复用的位置表。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 821. 字符的最短距离 | 简单 | 同样利用离当前位置最近的目标位置，本题求两个单词出现位置的最小距离。 |
| 244. 最短单词距离 II | 中等 | 当同一文本有多次查询时，预处理每个词的位置列表并双指针求最近距离。 |