LeetCode Solutions
245. Shortest Word Distance III
Time: $O(n)$ Space: $O(1)$
class Solution {
public:
int shortestWordDistance(vector<string>& words, string word1, string word2) {
const bool isSame = word1 == word2;
int ans = INT_MAX;
// If word1 == word2, index1 is the newest index
int index1 = words.size();
// If word1 == word2, index2 is the previous index
int index2 = -words.size();
for (int i = 0; i < words.size(); ++i) {
if (words[i] == word1) {
if (isSame)
index2 = index1;
index1 = i;
} else if (words[i] == word2) {
index2 = i;
}
ans = min(ans, abs(index1 - index2));
}
return ans;
}
};
class Solution {
public int shortestWordDistance(String[] words, String word1, String word2) {
final boolean isSame = word1.equals(word2);
int ans = Integer.MAX_VALUE;
int index1 = words.length; // If word1 == word2, index1 is the newest index
int index2 = -words.length; // If word1 == word2, index2 is the previous index
for (int i = 0; i < words.length; ++i) {
if (words[i].equals(word1)) {
if (isSame)
index2 = index1;
index1 = i;
} else if (words[i].equals(word2)) {
index2 = i;
}
ans = Math.min(ans, Math.abs(index1 - index2));
}
return ans;
}
}
class Solution:
def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
isSame = word1 == word2
ans = math.inf
# If word1 == word2, index1 is the newest index
index1 = len(wordsDict)
# If word1 == word2, index2 is the previous index
index2 = -len(wordsDict)
for i, word in enumerate(wordsDict):
if word == word1:
if isSame:
index2 = index1
index1 = i
elif word == word2:
index2 = i
ans = min(ans, abs(index1 - index2))
return ans