> 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/245shortest-word-distance-iii.md).

# 245\_Shortest Word Distance III

## 245. Shortest Word Distance III

Level: medium

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.
word1 and word2 may be the same and they represent two individual words in the list.

Note:
This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.
```

### Example1

```
Input: words = ["practice", "makes", "perfect", "coding", "makes"]
       word1 = “makes”
       word2 = “makes”
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|$$ but only consider the cases that

$$
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)
            if words[i] == word2:   # use if instead of elif
                p2.append(i)

        # find shortest distance
        distance = len(words)
        for i in p1:
            for j in p2:
                if i != j:          # don't update when i = j
                    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.

If word1 is not the same as word2, update shortest distance for each new location when we scan from left to right.

If word1 is the same as word2, only update the shortest distance for new location of word1.

### Complexity 2

* Time:$$O(n)$$ where $$n$$ is the length of the array 
* 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)
            if words[i] == word2:                      # use if instead of elif
               p2 = i
               if word1 != word2:                      # new line
                   distance = min(distance, i - p1)    # new line
        return distance
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lei-d.gitbook.io/leetcode/array/245shortest-word-distance-iii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.