LeetCode 245: Shortest Word Distance III (One Pass with Same-Word Handling)
LeetCode 245ArrayStringToday we solve LeetCode 245 - Shortest Word Distance III.
Source: https://leetcode.com/problems/shortest-word-distance-iii/
English
Problem Summary
Given wordsDict and two words, return the minimum index distance between occurrences. Unlike part I/II, word1 and word2 can be the same.
Key Insight
Track the latest seen positions while scanning once. If words are different, keep two indices; if equal, compare adjacent occurrences of that same word.
Optimal Algorithm Steps
1) Initialize answer to large value.
2) If word1 != word2, update idx1/idx2 when matched and minimize distance when both exist.
3) If word1 == word2, remember previous index of that word and minimize with current index.
4) Return answer.
Complexity Analysis
Time: O(n).
Space: O(1).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int shortestWordDistance(String[] wordsDict, String word1, String word2) {
int ans = Integer.MAX_VALUE;
if (word1.equals(word2)) {
int prev = -1;
for (int i = 0; i < wordsDict.length; i++) {
if (wordsDict[i].equals(word1)) {
if (prev != -1) ans = Math.min(ans, i - prev);
prev = i;
}
}
return ans;
}
int i1 = -1, i2 = -1;
for (int i = 0; i < wordsDict.length; i++) {
if (wordsDict[i].equals(word1)) i1 = i;
if (wordsDict[i].equals(word2)) i2 = i;
if (i1 != -1 && i2 != -1) ans = Math.min(ans, Math.abs(i1 - i2));
}
return ans;
}
}func shortestWordDistance(wordsDict []string, word1 string, word2 string) int {
const inf = int(^uint(0) >> 1)
ans := inf
if word1 == word2 {
prev := -1
for i, w := range wordsDict {
if w == word1 {
if prev != -1 && i-prev < ans { ans = i - prev }
prev = i
}
}
return ans
}
i1, i2 := -1, -1
for i, w := range wordsDict {
if w == word1 { i1 = i }
if w == word2 { i2 = i }
if i1 != -1 && i2 != -1 {
d := i1 - i2; if d < 0 { d = -d }
if d < ans { ans = d }
}
}
return ans
}class Solution {
public:
int shortestWordDistance(vector<string>& wordsDict, string word1, string word2) {
int ans = INT_MAX;
if (word1 == word2) {
int prev = -1;
for (int i = 0; i < (int)wordsDict.size(); i++) {
if (wordsDict[i] == word1) {
if (prev != -1) ans = min(ans, i - prev);
prev = i;
}
}
return ans;
}
int i1 = -1, i2 = -1;
for (int i = 0; i < (int)wordsDict.size(); i++) {
if (wordsDict[i] == word1) i1 = i;
if (wordsDict[i] == word2) i2 = i;
if (i1 != -1 && i2 != -1) ans = min(ans, abs(i1 - i2));
}
return ans;
}
};class Solution:
def shortestWordDistance(self, wordsDict: list[str], word1: str, word2: str) -> int:
ans = float('inf')
if word1 == word2:
prev = -1
for i, w in enumerate(wordsDict):
if w == word1:
if prev != -1:
ans = min(ans, i - prev)
prev = i
return ans
i1 = i2 = -1
for i, w in enumerate(wordsDict):
if w == word1:
i1 = i
if w == word2:
i2 = i
if i1 != -1 and i2 != -1:
ans = min(ans, abs(i1 - i2))
return ansvar shortestWordDistance = function(wordsDict, word1, word2) {
let ans = Number.MAX_SAFE_INTEGER;
if (word1 === word2) {
let prev = -1;
for (let i = 0; i < wordsDict.length; i++) {
if (wordsDict[i] === word1) {
if (prev !== -1) ans = Math.min(ans, i - prev);
prev = i;
}
}
return ans;
}
let i1 = -1, i2 = -1;
for (let i = 0; i < wordsDict.length; i++) {
if (wordsDict[i] === word1) i1 = i;
if (wordsDict[i] === word2) i2 = i;
if (i1 !== -1 && i2 !== -1) ans = Math.min(ans, Math.abs(i1 - i2));
}
return ans;
};中文
题目概述
给定单词数组 wordsDict 和两个目标词，返回它们出现位置的最小下标距离。本题允许 word1 与 word2 相同。
核心思路
单次扫描即可。若两个词不同，分别维护最近位置；若相同，则维护该词上一次出现位置并比较相邻出现距离。
最优算法步骤
1）初始化最小距离。
2）word1 != word2 时维护 i1、i2 并实时更新答案。
3）word1 == word2 时维护 prev 并比较 i - prev。
4）返回最小距离。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int shortestWordDistance(String[] wordsDict, String word1, String word2) {
int ans = Integer.MAX_VALUE;
if (word1.equals(word2)) {
int prev = -1;
for (int i = 0; i < wordsDict.length; i++) {
if (wordsDict[i].equals(word1)) {
if (prev != -1) ans = Math.min(ans, i - prev);
prev = i;
}
}
return ans;
}
int i1 = -1, i2 = -1;
for (int i = 0; i < wordsDict.length; i++) {
if (wordsDict[i].equals(word1)) i1 = i;
if (wordsDict[i].equals(word2)) i2 = i;
if (i1 != -1 && i2 != -1) ans = Math.min(ans, Math.abs(i1 - i2));
}
return ans;
}
}func shortestWordDistance(wordsDict []string, word1 string, word2 string) int {
const inf = int(^uint(0) >> 1)
ans := inf
if word1 == word2 {
prev := -1
for i, w := range wordsDict {
if w == word1 {
if prev != -1 && i-prev < ans { ans = i - prev }
prev = i
}
}
return ans
}
i1, i2 := -1, -1
for i, w := range wordsDict {
if w == word1 { i1 = i }
if w == word2 { i2 = i }
if i1 != -1 && i2 != -1 {
d := i1 - i2; if d < 0 { d = -d }
if d < ans { ans = d }
}
}
return ans
}class Solution {
public:
int shortestWordDistance(vector<string>& wordsDict, string word1, string word2) {
int ans = INT_MAX;
if (word1 == word2) {
int prev = -1;
for (int i = 0; i < (int)wordsDict.size(); i++) {
if (wordsDict[i] == word1) {
if (prev != -1) ans = min(ans, i - prev);
prev = i;
}
}
return ans;
}
int i1 = -1, i2 = -1;
for (int i = 0; i < (int)wordsDict.size(); i++) {
if (wordsDict[i] == word1) i1 = i;
if (wordsDict[i] == word2) i2 = i;
if (i1 != -1 && i2 != -1) ans = min(ans, abs(i1 - i2));
}
return ans;
}
};class Solution:
def shortestWordDistance(self, wordsDict: list[str], word1: str, word2: str) -> int:
ans = float('inf')
if word1 == word2:
prev = -1
for i, w in enumerate(wordsDict):
if w == word1:
if prev != -1:
ans = min(ans, i - prev)
prev = i
return ans
i1 = i2 = -1
for i, w in enumerate(wordsDict):
if w == word1:
i1 = i
if w == word2:
i2 = i
if i1 != -1 and i2 != -1:
ans = min(ans, abs(i1 - i2))
return ansvar shortestWordDistance = function(wordsDict, word1, word2) {
let ans = Number.MAX_SAFE_INTEGER;
if (word1 === word2) {
let prev = -1;
for (let i = 0; i < wordsDict.length; i++) {
if (wordsDict[i] === word1) {
if (prev !== -1) ans = Math.min(ans, i - prev);
prev = i;
}
}
return ans;
}
let i1 = -1, i2 = -1;
for (let i = 0; i < wordsDict.length; i++) {
if (wordsDict[i] === word1) i1 = i;
if (wordsDict[i] === word2) i2 = i;
if (i1 !== -1 && i2 !== -1) ans = Math.min(ans, Math.abs(i1 - i2));
}
return ans;
};
Comments