LeetCode 面试题 17.11. 单词距离
目录
题目描述
题意分析
在单词数组中找
word1与word2两次出现位置的最小下标距离。题目保证两个目标单词不同且都出现过。暴力枚举两组出现位置需要
O(pq)。按数组从左到右扫描时，只需记住两个单词各自最近一次出现的位置：当前遇到某个目标词后，它与另一个词最近位置的距离，一定不大于它与更早位置的距离。这条单调性允许永久丢弃旧位置，把空间压到常数。
解法：维护两个最近位置
核心思路
last1、last2分别表示扫描前缀里 word1、word2 的最后位置。每遇到一个目标词就更新对应位置；当两个位置都有效时，用绝对差更新答案。循环不变量是：处理完下标 i 后，
last1/last2是各自不超过 i 的最大出现下标，answer 是前缀[0,i]中所有有效词对的最小距离。为什么只保留最近位置不会漏解？当前新位置 k 与另一个单词的多个历史位置比较时，最大的历史下标离 k 最近；更早位置距离只会更大。
例：
words=["I","am","a","student","from","a","university"]，word1="a"、word2="student"。扫描到 2 记录 last1=2；扫描到 3 记录 last2=3，距离更新为 1。后面的 a 在 5，和 student 距离 2，不会改善，答案仍是 1。
解题步骤
- 两个最近位置初始化为 -1，答案初始化为数组长度。
- 扫描下标 i；命中 word1 就更新 last1，命中 word2 就更新 last2。
- 两个位置都不为 -1 时更新最小绝对差。
- 返回答案。
代码实现
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)，数组只扫描一次。- 空间复杂度：
O(1)，只记录两个下标和答案。
关键点总结
- 对当前出现位置，另一个单词的最近历史位置一定最优，旧位置可以丢弃。
- 必须等两个位置都有效后再计算距离，避免哨兵参与答案。
- Java 字符串用
equals比内容，不能用==。- 面试追问若同一数组要回答很多次查询，应预处理“单词 → 有序下标列表”，每次用双指针在两条列表上求最短距离。
易错点总结
- 错误写法：让位置初值参与距离计算。反例中目标词第一次出现在下标 5；若用 0 表示“未出现”，就可能虚构出距离 5。应使用 -1 并检查有效性。
- 只记录第一次出现：
["a","x","b","a"]查询 a、b，第一次 a 与 b 距离 2，最近 a 与 b 距离 1。- Java 用
words[i] == word1：内容相同但对象不同的字符串会比较失败，最终答案保持初值。- 每次命中后与另一个词的所有历史位置比较：结果正确但退化为平方级；最近位置已经足够。
- 把距离写成下标差而不取绝对值：word2 出现在 word1 之后时得到负数并错误成为最小值。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 244. 最短单词距离 II | 中等 | 多次查询时预处理位置列表 |
| 245. 最短单词距离 III | 中等 | 两个查询词可能相同 |