Shortest Word Distance 2

题目描述

This is a follow up of Shortest Word Distance.

The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

解题方法

2的区别是需要不断地call, 并且每次的word也不同，所以我们肯定要记录下所有word的位置信息 以备后面使用。而当输入一个word的时候也需要快速的查询，我们可以想到用hashtable来 保存位置信息可以达到O(1)的查找时间。

因为word不一定只出现一次，所以我们hashtable的value是一个list。

两个List之间找最小distance的code有点类似merge two sorted list

Solution

class WordDistance(object):
    def __init__(self, words):
        """
        initialize your data structure here.
        :type words: List[str]
        """
        self.dic = {}
        for idx, word in enumerate(words):
            if word in self.dic:
                self.dic[word].append(idx)
            else:
                self.dic[word] = [idx]

    def shortest(self, word1, word2):
        """
        Adds a word into the data structure.
        :type word1: str
        :type word2: str
        :rtype: int
        """
        list1 = self.dic[word1]
        list2 = self.dic[word2]

        p1, p2 = 0, 0
        minDis = sys.maxint
        while p1 < len(list1) and p2 < len(list2):
            diff = abs(list1[p1] - list2[p2])
            minDis = minDis if minDis < diff else diff
            if list1[p1] < list2[p2]:
                p1 += 1
            else:
                p2 += 1

        return minDis

Reference