Shortest Word Distance II

这道题一开始想通过init函数写一个O(n^2)的算法把所有工作一劳永逸的搞定，然后shortest就是O(1)的时间复杂度了，但是大case过不了，所以这里只能通过两个O(n)的算法（shortest函数无法界定，非要说的话就是O(j+k)，j和k都是两个词在words列表里面出现的次数）解决问题了

class WordDistance(object):

    def __init__(self, words):
        """
        :type words: List[str]
        """
        self.store = {}
        for index, word in enumerate(words):
            self.store.setdefault(word, [])
            self.store[word].append(index)

    def shortest(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        result = sys.maxint
        for index1 in self.store[word1]:
            for index2 in self.store[word2]:
                result = min(abs(index1 - index2), result)

        return result

这就是最优了？并不是，shortest函数我们还可以把两个循环放在一起，利用第一题的翻滚向前的思路来写，这样时间复杂度从O(j + k)变成了O(min(j, k))，上升不多，但是因为极端case的存在，这样的逻辑表现肯定更好

class WordDistance(object):

    def __init__(self, words):
        """
        :type words: List[str]
        """
        self.store = {}
        for index, word in enumerate(words):
            self.store.setdefault(word, [])
            self.store[word].append(index)

    def shortest(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        result = sys.maxint
        n, m = len(self.store[word1]), len(self.store[word2])
        i, j = 0, 0
        while i < n and j < m:
            result = min(abs(self.store[word1][i] - self.store[word2][j]), result)
            if self.store[word1][i] < self.store[word2][j]:
                i += 1
            else:
                j += 1

        return result