# 245. Shortest Word Distance III

## Approach 1: Storing list of indices of both words

```python
class Solution(object):
    def shortestWordDistance(self, words, word1, word2):
        """
        :type words: List[str]
        :type word1: str
        :type word2: str
        :rtype: int
        """
        word1s = []
        word2s = []
        for i in range(len(words)):
            if words[i] == word1:
                word1s.append(i)
            if words[i] == word2:
                word2s.append(i)
        mi = float('inf')
        for i in word1s:
            for j in word2s:
                if i != j:
                    mi = min(abs(i-j), mi)
        return mi
```

For both the words we store the indices of all the positions they occur in. Once we have that we can easily iterate through both of these individual lists and find the minimum difference

> **Time Complexity:** *O(N^2)*
>
> **Space Complexity:** *O(N)* 

## Approach 2: Iterating through list but storing only last seen index of each word

```python
class Solution(object):
    def shortestWordDistance(self, words, word1, word2):
        """
        :type words: List[str]
        :type word1: str
        :type word2: str
        :rtype: int
        """
        idx1 = idx2 = res = float('inf')
        if word1 == word2:
            for i,word in enumerate(words):
                if word == word1:
                    idx1 = idx2 
                    idx2 = i
                    res = min(res,abs(idx2-idx1))
        else:
            for i,word in enumerate(words):
                if word == word1:
                    idx1 = i
                    res = min(res,abs(idx1-idx2))
                elif word == word2:
                    idx2 = i
                    res = min(res,abs(idx1-idx2))
        return res
```

In this approach instead of storing lists of indices we just need to store the last seen one. Each time we see one of the words we just calculate the difference between the two last seen indices and update it if it smaller than the shortest distance we've seen before

> **Time Complexity:** *O(N)*
>
> **Space Complexity:** *O(1)*