LeetCode Solutions
243. Shortest Word Distance
Time: $O(n)$ Space: $O(1)$
class Solution {
public:
int shortestDistance(vector<string>& wordsDict, string word1, string word2) {
int ans = wordsDict.size();
int index1 = -1; // wordsDict[index1] == word1
int index2 = -1; // wordsDict[index2] == word2
for (int i = 0; i < wordsDict.size(); ++i) {
if (wordsDict[i] == word1) {
index1 = i;
if (index2 != -1)
ans = min(ans, index1 - index2);
}
if (wordsDict[i] == word2) {
index2 = i;
if (index1 != -1)
ans = min(ans, index2 - index1);
}
}
return ans;
}
};
class Solution {
public int shortestDistance(String[] wordsDict, String word1, String word2) {
int ans = wordsDict.length;
int index1 = -1; // wordsDict[index1] == word1
int index2 = -1; // wordsDict[index2] == word2
for (int i = 0; i < wordsDict.length; ++i) {
if (wordsDict[i].equals(word1)) {
index1 = i;
if (index2 != -1)
ans = Math.min(ans, index1 - index2);
}
if (wordsDict[i].equals(word2)) {
index2 = i;
if (index1 != -1)
ans = Math.min(ans, index2 - index1);
}
}
return ans;
}
}
class Solution:
def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
ans = len(wordsDict)
index1 = -1 # wordsDict[index1] == word1
index2 = -1 # wordsDict[index2] == word2
for i, word in enumerate(wordsDict):
if word == word1:
index1 = i
if index2 != -1:
ans = min(ans, index1 - index2)
if word == word2:
index2 = i
if index1 != -1:
ans = min(ans, index2 - index1)
return ans