0243._Shortest_Word_Distance.md

243. Shortest Word Distance

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/shortest-word-distance/description/

内容描述

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

Example:
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Input: word1 = “coding”, word2 = “practice”
Output: 3
Input: word1 = "makes", word2 = "coding"
Output: 1
Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******

把每个word出现的位置全部记下来，然后取位置差的最小绝对值即可

worst case就是words里面只有word1和word2两个元素，然后这样相当于所有的idx全部做两遍for loop

平均下来应该不至于那么慢

beats 43.27%

class Solution(object):
    def shortestDistance(self, words, word1, word2):
        """
        :type words: List[str]
        :type word1: str
        :type word2: str
        :rtype: int
        """
        lookup = collections.defaultdict(list)
        for idx, word in enumerate(words):
            lookup[word].append(idx)
        idxes_1 = lookup[word1]
        idxes_2 = lookup[word2]
        res = sys.maxsize
        for i in idxes_1:
            for j in idxes_2:
                res = min(res, abs(i-j))
        return res

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******

进行一遍循环，同时用两个指针指向word1和word2出现的位置，每次出现word1或word2就更新他们相应指针的位置，并且每次都更新一下res

beats 98.78%

class Solution(object):
    def shortestDistance(self, words, word1, word2):
        """
        :type words: List[str]
        :type word1: str
        :type word2: str
        :rtype: int
        """
        idx1, idx2, res = -1, -1, sys.maxsize
        for idx, word in enumerate(words):
            if word == word1:
                idx1 = idx
            if word == word2:
                idx2 = idx
            if idx1 != -1 and idx2 != -1:
                res = min(res, abs(idx1-idx2))
        return res