> For the complete documentation index, see [llms.txt](https://lei-d.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lei-d.gitbook.io/leetcode/array/244shortest-word-distance-ii.md).

# 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](https://leetcode.com/problems/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

```python
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)
```