LeetCode 243: Shortest Word Distance (One-Pass Last-Seen Indices)
LeetCode 243ArrayStringToday we solve LeetCode 243 - Shortest Word Distance.
Source: https://leetcode.com/problems/shortest-word-distance/
English
Problem Summary
Given an array wordsDict and two different words word1, word2, return the minimum index distance between any occurrence of word1 and word2.
Key Insight
During a single left-to-right pass, keep the latest index of word1 and word2. Whenever both are known, update answer with abs(i1 - i2). The latest positions are always enough because any future better answer must involve one of them.
Brute Force and Limitations
Brute force checks all pairs of positions where words match targets and takes minimum distance. If word1 appears a times and word2 appears b times, complexity is O(a*b), worst-case O(n^2).
Optimal Algorithm Steps
1) Initialize idx1 = -1, idx2 = -1, ans = n.
2) Scan array once.
3) If current word equals word1 update idx1; if equals word2 update idx2.
4) If both indices are valid, update ans = min(ans, abs(idx1 - idx2)).
5) Return ans.
Complexity Analysis
Time: O(n).
Space: O(1).
Common Pitfalls
- Forgetting that word1 and word2 are guaranteed different in this problem.
- Updating answer before both indices are initialized.
- Returning a hardcoded large number when input assumptions are violated in custom tests.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int shortestDistance(String[] wordsDict, String word1, String word2) {
int idx1 = -1, idx2 = -1;
int ans = wordsDict.length;
for (int i = 0; i < wordsDict.length; i++) {
if (wordsDict[i].equals(word1)) idx1 = i;
if (wordsDict[i].equals(word2)) idx2 = i;
if (idx1 != -1 && idx2 != -1) {
ans = Math.min(ans, Math.abs(idx1 - idx2));
}
}
return ans;
}
}func shortestDistance(wordsDict []string, word1 string, word2 string) int {
idx1, idx2 := -1, -1
ans := len(wordsDict)
for i, w := range wordsDict {
if w == word1 {
idx1 = i
}
if w == word2 {
idx2 = i
}
if idx1 != -1 && idx2 != -1 {
d := idx1 - idx2
if d < 0 {
d = -d
}
if d < ans {
ans = d
}
}
}
return ans
}class Solution {
public:
int shortestDistance(vector<string>& wordsDict, string word1, string word2) {
int idx1 = -1, idx2 = -1;
int ans = (int)wordsDict.size();
for (int i = 0; i < (int)wordsDict.size(); ++i) {
if (wordsDict[i] == word1) idx1 = i;
if (wordsDict[i] == word2) idx2 = i;
if (idx1 != -1 && idx2 != -1) {
ans = min(ans, abs(idx1 - idx2));
}
}
return ans;
}
};from typing import List
class Solution:
def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
idx1 = idx2 = -1
ans = len(wordsDict)
for i, w in enumerate(wordsDict):
if w == word1:
idx1 = i
if w == word2:
idx2 = i
if idx1 != -1 and idx2 != -1:
ans = min(ans, abs(idx1 - idx2))
return ansvar shortestDistance = function(wordsDict, word1, word2) {
let idx1 = -1, idx2 = -1;
let ans = wordsDict.length;
for (let i = 0; i < wordsDict.length; i++) {
if (wordsDict[i] === word1) idx1 = i;
if (wordsDict[i] === word2) idx2 = i;
if (idx1 !== -1 && idx2 !== -1) {
ans = Math.min(ans, Math.abs(idx1 - idx2));
}
}
return ans;
};中文
题目概述
给定字符串数组 wordsDict，以及两个不同单词 word1 和 word2，求它们在数组中任意两次出现位置的最小下标距离。
核心思路
一次遍历过程中，持续记录 word1 和 word2 最近一次出现的下标。只要两个下标都出现过，就可以即时计算并更新最小距离。这个“最近位置”不变量保证了线性复杂度下仍能得到全局最优。
暴力解法与不足
暴力法先收集两个词的全部下标，再做两两比较，时间最坏可到 O(n^2)。当数组很长、目标词出现频繁时开销明显过大。
最优算法步骤
1）初始化 idx1 = -1、idx2 = -1、ans = n。
2）从左到右遍历数组。
3）遇到 word1 更新 idx1，遇到 word2 更新 idx2。
4）若两个下标都已有效，则用 abs(idx1 - idx2) 更新最小值。
5）遍历结束返回 ans。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。
常见陷阱
- 在两个下标尚未都出现时就参与最小值比较。
- 把本题和 LeetCode 245（允许同词）混淆，导致状态转移写错。
- 自测时没有覆盖“两个词只出现一次”的情况。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int shortestDistance(String[] wordsDict, String word1, String word2) {
int idx1 = -1, idx2 = -1;
int ans = wordsDict.length;
for (int i = 0; i < wordsDict.length; i++) {
if (wordsDict[i].equals(word1)) idx1 = i;
if (wordsDict[i].equals(word2)) idx2 = i;
if (idx1 != -1 && idx2 != -1) {
ans = Math.min(ans, Math.abs(idx1 - idx2));
}
}
return ans;
}
}func shortestDistance(wordsDict []string, word1 string, word2 string) int {
idx1, idx2 := -1, -1
ans := len(wordsDict)
for i, w := range wordsDict {
if w == word1 {
idx1 = i
}
if w == word2 {
idx2 = i
}
if idx1 != -1 && idx2 != -1 {
d := idx1 - idx2
if d < 0 {
d = -d
}
if d < ans {
ans = d
}
}
}
return ans
}class Solution {
public:
int shortestDistance(vector<string>& wordsDict, string word1, string word2) {
int idx1 = -1, idx2 = -1;
int ans = (int)wordsDict.size();
for (int i = 0; i < (int)wordsDict.size(); ++i) {
if (wordsDict[i] == word1) idx1 = i;
if (wordsDict[i] == word2) idx2 = i;
if (idx1 != -1 && idx2 != -1) {
ans = min(ans, abs(idx1 - idx2));
}
}
return ans;
}
};from typing import List
class Solution:
def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
idx1 = idx2 = -1
ans = len(wordsDict)
for i, w in enumerate(wordsDict):
if w == word1:
idx1 = i
if w == word2:
idx2 = i
if idx1 != -1 and idx2 != -1:
ans = min(ans, abs(idx1 - idx2))
return ansvar shortestDistance = function(wordsDict, word1, word2) {
let idx1 = -1, idx2 = -1;
let ans = wordsDict.length;
for (let i = 0; i < wordsDict.length; i++) {
if (wordsDict[i] === word1) idx1 = i;
if (wordsDict[i] === word2) idx2 = i;
if (idx1 !== -1 && idx2 !== -1) {
ans = Math.min(ans, Math.abs(idx1 - idx2));
}
}
return ans;
};
Comments