# 243\_Shortest Word Distance

## 243. Shortest Word Distance

Level: easy

Tag: array

## Question

```
Given a list of words and two words word1 and word2, 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 1 (brute force)

Find all the positions $$p_1,p_2$$ for word1 and word2, and compute the shortest distance by minimizing $$|p_1 - p_2|$$.

### Complexity 1

* Time:$$O(n+k^2)$$ where $$n$$ is the length of the array and  $$k$$ is the maximum number of word1 and word2.
* Space:$$O(k)$$

### Solution 1

```python
class Solution(object):
    def shortestDistance(self, words, word1, word2):
        """
        :type words: List[str]
        :type word1: str
        :type word2: str
        :rtype: int
        """

        p1, p2 = [], []

        # find position for word1 and word2
        for i in range(len(words)):
            if words[i] == word1:
                p1.append(i)
            elif words[i] == word2:
                p2.append(i)

        # find shortest distance
        distance = len(words)
        for i in p1:
            for j in p2:
                distance = min(distance, abs(i-j))

        return distance
```

### Idea 2 (greedy)

Keep two indices $$p_1,p_2$$ where we store the most recent locations of word1 and word2. Update shortest distance when we scan from left to right.

### Complexity 2

* Time:$$O(n)$$ where $$n$$ is the length of the array&#x20;
* Space:$$O(1)$$

### Solution 2

```python
class Solution(object):
    def shortestDistance(self, words, word1, word2):
        """
        :type words: List[str]
        :type word1: str
        :type word2: str
        :rtype: int
        """

        n = len(words)
        distance = n
        p1 = p2 = -n
        for i in range(n):
            if words[i] == word1:
               p1 = i
               distance = min(distance, i - p2)
            elif words[i] == word2:
               p2 = i
               distance = min(distance, i - p1)
        return distance
```
