Question

245. Shortest Word Distance III

中文文档

Description

Given an array of strings wordsDict and two strings that already exist in the array word1 and word2, return _the shortest distance between the occurrence of these two words in the list_.

Note that word1 and word2 may be the same. It is guaranteed that they represent two individual words in the list.

 

Example 1:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

Example 2:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "makes"
Output: 3

 

Constraints:

• 1 <= wordsDict.length <= 105
• 1 <= wordsDict[i].length <= 10
• wordsDict[i] consists of lowercase English letters.
• word1 and word2 are in wordsDict.

Solutions

Solution 1

class Solution:
  def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
    ans = len(wordsDict)
    if word1 == word2:
      j = -1
      for i, w in enumerate(wordsDict):
        if w == word1:
          if j != -1:
            ans = min(ans, i - j)
          j = i
    else:
      i = j = -1
      for k, w in enumerate(wordsDict):
        if w == word1:
          i = k
        if w == word2:
          j = k
        if i != -1 and j != -1:
          ans = min(ans, abs(i - j))
    return ans

class Solution {
  public int shortestWordDistance(String[] wordsDict, String word1, String word2) {
    int ans = wordsDict.length;
    if (word1.equals(word2)) {
      for (int i = 0, j = -1; i < wordsDict.length; ++i) {
        if (wordsDict[i].equals(word1)) {
          if (j != -1) {
            ans = Math.min(ans, i - j);
          }
          j = i;
        }
      }
    } else {
      for (int k = 0, i = -1, j = -1; k < wordsDict.length; ++k) {
        if (wordsDict[k].equals(word1)) {
          i = k;
        }
        if (wordsDict[k].equals(word2)) {
          j = k;
        }
        if (i != -1 && j != -1) {
          ans = Math.min(ans, Math.abs(i - j));
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  int shortestWordDistance(vector<string>& wordsDict, string word1, string word2) {
    int n = wordsDict.size();
    int ans = n;
    if (word1 == word2) {
      for (int i = 0, j = -1; i < n; ++i) {
        if (wordsDict[i] == word1) {
          if (j != -1) {
            ans = min(ans, i - j);
          }
          j = i;
        }
      }
    } else {
      for (int k = 0, i = -1, j = -1; k < n; ++k) {
        if (wordsDict[k] == word1) {
          i = k;
        }
        if (wordsDict[k] == word2) {
          j = k;
        }
        if (i != -1 && j != -1) {
          ans = min(ans, abs(i - j));
        }
      }
    }
    return ans;
  }
};

func shortestWordDistance(wordsDict []string, word1 string, word2 string) int {
  ans := len(wordsDict)
  if word1 == word2 {
    j := -1
    for i, w := range wordsDict {
      if w == word1 {
        if j != -1 {
          ans = min(ans, i-j)
        }
        j = i
      }
    }
  } else {
    i, j := -1, -1
    for k, w := range wordsDict {
      if w == word1 {
        i = k
      }
      if w == word2 {
        j = k
      }
      if i != -1 && j != -1 {
        ans = min(ans, abs(i-j))
      }
    }
  }
  return ans
}

func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}