Skip to content

244. Shortest Word Distance II

  • Time:
    • Constructor: $O(|\texttt{words}|)$
    • shortest(word1: str, word2: str): $O(|\texttt{word1}| + |\texttt{word2}|)$
  • Space: $O(|\texttt{word1}| + |\texttt{word2}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class WordDistance {
 public:
  WordDistance(vector<string>& words) {
    for (int i = 0; i < words.size(); ++i)
      wordToIndices[words[i]].push_back(i);
  }

  int shortest(string word1, string word2) {
    const vector<int> indices1 = wordToIndices[word1];
    const vector<int> indices2 = wordToIndices[word2];
    int ans = INT_MAX;

    for (int i = 0, j = 0; i < indices1.size() && j < indices2.size();) {
      ans = min(ans, abs(indices1[i] - indices2[j]));
      if (indices1[i] < indices2[j])
        ++i;
      else
        ++j;
    }

    return ans;
  }

 private:
  unordered_map<string, vector<int>> wordToIndices;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class WordDistance {
  public WordDistance(String[] words) {
    for (int i = 0; i < words.length; ++i) {
      wordToIndices.putIfAbsent(words[i], new ArrayList<>());
      wordToIndices.get(words[i]).add(i);
    }
  }

  public int shortest(String word1, String word2) {
    List<Integer> indices1 = wordToIndices.get(word1);
    List<Integer> indices2 = wordToIndices.get(word2);
    int ans = Integer.MAX_VALUE;

    for (int i = 0, j = 0; i < indices1.size() && j < indices2.size();) {
      ans = Math.min(ans, Math.abs(indices1.get(i) - indices2.get(j)));
      if (indices1.get(i) < indices2.get(j))
        ++i;
      else
        ++j;
    }

    return ans;
  }

  private Map<String, List<Integer>> wordToIndices = new HashMap<>();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class WordDistance:
  def __init__(self, wordsDict: list[str]):
    self.wordToIndices = collections.defaultdict(list)
    for i, word in enumerate(wordsDict):
      self.wordToIndices[word].append(i)

  def shortest(self, word1: str, word2: str) -> int:
    indices1 = self.wordToIndices[word1]
    indices2 = self.wordToIndices[word2]
    ans = math.inf

    i = 0
    j = 0
    while i < len(indices1) and j < len(indices2):
      ans = min(ans, abs(indices1[i] - indices2[j]))
      if indices1[i] < indices2[j]:
        i += 1
      else:
        j += 1

    return ans