244_Shortest Word Distance II

244. Shortest Word Distance II

Level: medium

Tag: array, design

Question

This is a follow up of Shortest Word Distance.

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.

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

Example1

Input: words = ["practice", "makes", "perfect", "coding", "makes"]
       word1 = “coding”
       word2 = “practice”
Output: 3

Idea (greedy)

Use a dictionary to store the positions for all the unique words. Given word1 and word2, find their positions, and compute the smallest distance.

Complexity 2

• Time:$O(n+m)$ where $n$ is the length of the array, $m$ is the maximum of the number of word1 and word2.

• Space:$O(n)$

Solution 2

class WordDistance(object):

    def __init__(self, words):
        """
        :type words: List[str]
        """

        # construct a dictionary to store the position of each word
        self.dict = {}
        for i, w in enumerate(words):
            self.dict[w] = self.dict.get(w, []) + [i]


    def shortest(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        a, b = self.dict.get(word1), self.dict.get(word2)
        m, n = len(a), len(b)
        res = sys.maxsize
        i, j = 0, 0

        # find the shortest distance
        while i < m and j < n:
            res = min(res, abs(a[i] - b[j]))
            if a[i] < b[j]:
                i += 1
            else:
                j += 1

        return res



# Your WordDistance object will be instantiated and called as such:
# obj = WordDistance(words)
# param_1 = obj.shortest(word1,word2)