> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/array/245.-shortest-word-distance-iii.md).

# 245. Shortest Word Distance III

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.

**Example:**\
Assume that words = `["practice", "makes", "perfect", "coding", "makes"]`.

```
Input: word1 = “makes”, word2 = “coding”
Output: 1
```

```
Input: word1 = "makes", word2 = "makes"
Output: 3
```

**Note:**\
You may assume *word1* and *word2* are both in the list.

```cpp
// Brute Force
int shortestWordDistance(vector<string>& words, string word1, string word2) { // time: O(n^2); space: O(1)
    if (words.empty()) return 0;
    int n = words.size(), res = INT_MAX;
    for (int i = 0; i < n; ++i) {
        if (words[i] != word1) continue;
        for (int j = 0; j < n; ++j) {
            if (words[j] != word2 || j == i) continue;
            res = min(res, abs(i - j));
        }
    }
    return res;
}
```

```cpp
// Optimized method
int shortestWordDistance(vector<string>& words, string word1, string word2) { // time: O(n); space: O(1)
    int idx1 = -1, idx2 = -1, res = words.size();
    for (int i = 0; i < words.size(); ++i) {
        int t = idx1; // for duplicates
        if (words[i] == word1) {
            idx1 = i;
        }
        if (words[i] == word2) {
            idx2 = i;
        }
        if (idx1 != -1 && idx2 != -1) {
            if (word1 == word2 && t != -1 && t != idx1) {
                res = min(res, abs(idx1 - t));
            } else if (idx1 != idx2) {
                res = min(res, abs(idx1 - idx2));
            }
        }
    }
    return res;
}
```

```cpp
// Optimized method
int shortestWordDistance(vector<string>& words, string word1, string word2) { // time: O(n); space: O(1)
    int idx1 = words.size(), idx2 = -words.size(), res = INT_MAX;
    for (int i = 0; i < words.size(); ++i) {
        if (words[i] == word1) idx1 = word1 == word2 ? idx2 : i;
        if (words[i] == word2) idx2 = i;
        res = min(res, abs(idx1 - idx2));
    }
    return res;
}
```

```cpp
// Optimized method
int shortestWordDistance(vector<string>& words, string word1, string word2) { // time: O(n); space: O(1)
    int idx = -1, res = words.size();
    for (int i = 0; i < words.size(); ++i) {
        if (words[i] == word1 || words[i] == word2) {
            if (idx != -1 && (word1 == word2 || words[idx] != words[i])) {
                res = min(res, i - idx);
            }
            idx = i;
        }
    }
    return res;
}
```