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