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