# 244 Shortest Word Distance II

This is a **follow up** of [Shortest Word Distance](https://leetcode.com/problems/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.

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.

**The Idea:** First I considered doing O(n^2) preprocessing and create a lookup table to find the shortest distances between words, but this got TLE. The alternative approach would be to just map the occurrences into a dictionary and return the return the minimum absolute difference between the two lists in linear time. This gets AC, but repeatedly calling this more than N times would in worst case have a higher complexity than O(n^2) time.

**Complexity:** O(n) time for `init` and `shortest`. O(n) space.

```python
from collections import defaultdict
import sys


class WordDistance:

    def __init__(self, words):
        """
        :type words: List[str]
        """
        self.d = defaultdict(list)
        for i, word in enumerate(words):
            self.d[word].append(i)


    def shortest(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """

        if word1 == word2:
            return 0

        dist = sys.maxsize
        for loc1 in self.d[word1]:
            for loc2 in self.d[word2]:
                dist = min(dist, abs(loc1 - loc2))
        return dist

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