245. Shortest Word Distance III

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

word1 and word2 may be the same and they represent two individual words in the list.

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

Input: word1 = “makes”, word2 = “coding”
Output: 1

Input: word1 = "makes", word2 = "makes"
Output: 3

Note: You may assume word1 and word2 are both in the list.

解题要点：

与第二题相似，不同的是要单独处理两个word一样的情况。

class Solution(object):
    def shortestWordDistance(self, words, word1, word2):
        """
        :type words: List[str]
        :type word1: str
        :type word2: str
        :rtype: int
        """
        mydict = collections.defaultdict(list)
        for i, k in enumerate(words):
            mydict[k].append(i)
        
        loc1 = mydict[word1]
        loc2 = mydict[word2]
        w1 = w2 = 0
        res = sys.maxint
        if word1 == word2: 
            for i in range(len(loc1)-1):
                res = min(res, abs(loc1[i+1] - loc1[i]))
        else:
            while w1 < len(loc1) and w2 < len(loc2):
                res = min(res, abs(loc1[w1] - loc2[w2]))
                if loc1[w1] < loc2[w2]:
                    w1 += 1
                else:
                    w2 += 1
        return res