243_最短单词距离

类型：数组

• 243. 最短单词距离 💚

  https://leetcode-cn.com/problems/shortest-word-distance/

  ❓ 给定一个单词列表和两个单词 word1 和 word2，返回列表中这两个单词之间的最短距离。

  输入：words = [“practice”, “makes”, “perfect”, “coding”, “makes”]

  输入：word1 = “coding”, word2 = “practice”

  输出：3

  💡 一次遍历

  如果使用暴力遍历的话，我们需要 O(n) 来遍历第一个单词，又需要 O(n) 来遍历第二个单词。时间复杂度为O(n^2).

  我们可以通过记录两个下标 i1 和 i2 来优化时间，二者分别保存 word1 和 word2 最近出现的位置。每次发现单词新的出现位置时，我们无需遍历数组去寻找另一个单词，因为我们已经记录了其之前出现的最近下标。只需要计算并更新记录即可。

  class Solution:
      def shortestDistance(self, words: List[str], word1: str, word2: str) -> int:
          lastIndex1 = -1
          lastIndex2 = -1
          minDistance = len(words)
          for i in range(len(words)):
              if words[i] == word1:
                  lastIndex1 = i
                  if lastIndex2 >= 0 and i - lastIndex2 < minDistance:
                      minDistance = i - lastIndex2
              elif words[i] == word2:
                  lastIndex2 = i
                  if lastIndex1 >= 0 and i - lastIndex1 < minDistance:
                      minDistance = i - lastIndex1
          return minDistance

  时间复杂度：O(n)，空间复杂度：O(1)