245. Shortest Word Distance III

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public: int shortestWordDistance(vector& 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; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 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