## 243. Shortest Word Distance

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example,
Assume that words = `["practice", "makes", "perfect", "coding", "makes"]`.

Given word1 = `“coding”`, word2 = `“practice”`, return 3.
Given word1 = `"makes"`, word2 = `"coding"`, return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

b'
\n\n

## Solution

\n

This is a straight-forward coding problem. The distance between any two positions and in an array is . To find the shortest distance between `word1` and `word2`, we need to traverse the input array and find all occurrences and of the two words, and check if is less than the minimum distance computed so far.

\n
\n

#### Approach #1 (Brute Force) [Accepted]

\n

Algorithm

\n

A naive solution to this problem is to go through the entire array looking for the first word. Every time we find an occurrence of the first word, we search the entire array for the closest occurrence of the second word.

\n

Java

\n
`public int shortestDistance(String[] words, String word1, String word2) {\n    int minDistance = words.length;\n    for (int i = 0; i < words.length; i++) {\n        if (words[i].equals(word1)) {\n            for (int j = 0; j < words.length; j++) {\n                if (words[j].equals(word2)) {\n                    minDistance = Math.min(minDistance, Math.abs(i - j));\n                }\n            }\n        }\n    }\n    return minDistance;\n}\n`
\n

Complexity Analysis

\n

The time complexity is , since for every occurrence of `word1`, we traverse the entire array in search for the closest occurrence of `word2`.

\n

Space complexity is , since no additional space is used.

\n
\n

#### Approach #2 (One-pass) [Accepted]

\n

Algorithm

\n

We can greatly improve on the brute-force approach by keeping two indices `i1` and `i2` where we store the most recent locations of `word1` and `word2`. Each time we find a new occurrence of one of the words, we do not need to search the entire array for the other word, since we already have the index of its most recent occurrence.

\n

Java

\n
`public int shortestDistance(String[] words, String word1, String word2) {\n    int i1 = -1, i2 = -1;\n    int minDistance = words.length;\n    int currentDistance;\n    for (int i = 0; i < words.length; i++) {\n        if (words[i].equals(word1)) {\n            i1 = i;\n        } else if (words[i].equals(word2)) {\n            i2 = i;\n        }\n\n        if (i1 != -1 && i2 != -1) {\n            minDistance = Math.min(minDistance, Math.abs(i1 - i2));\n        }\n    }\n    return minDistance;\n}\n`
\n

Complexity Analysis

\n

The time complexity is . This problem is inherently linear; we cannot do better than because at the very least, we have to read the entire input.

\n

Space complexity is , since no additional space is allocated.

\n

Analysis written by: @noran

\n
'