Shortest Word Distance

题目描述

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

For example, Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = "coding", word2 = "practice", return 3. Given word1 = "makes", word2 = "coding", return 1.

Note: You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

解题方法

1比较简单，只需要用两个variable来记录word1和word2出现过的位置就可以，随着loop往 后，我们只需要记录最后一次出现的位置就可以得到shortest distance

Solution

class Solution(object):
    def shortestDistance(self, words, word1, word2):
        """
        :type words: List[str]
        :type word1: str
        :type word2: str
        :rtype: int
        """
        if not words:
            return -1
        length = len(words)
        result = sys.maxint
        index1 = -1
        index2 = -1
        for idx, word in enumerate(words):
            if word == word1:
                index1 = idx
                if index2 != -1:
                    newDis = index1 - index2
                    if newDis < result:
                        result = newDis
            elif word == word2:
                index2 = idx
                if index1 != -1:
                    newDis = index2 - index1
                    if newDis < result:
                        result = newDis

        return result

Reference