# Shortest Word Distance

Problem Source: LeetCode

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

### Example:

Assume that words = [“apple”, “oranges”, “mango”, “oranges”, “fruit”].

Input: word1 = “mango”, word2 = “apple”

Output: 2

Input: word1 = “oranges”, word2 = “fruit”

Output: 1

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

### Solution:

This problem can be implemented easily using brute force but the time complexity will not be appreciable. But we can greatly improve brute force algorithm by iterating it only once and storing the latest indexes of the `word1` and `word2`. This means the time complexity is greatly reduced hence efficiency is maximized.

### Implementation

#### Java

``` public static class Solution {
public int shortestDistance(String[] words, String word1, String word2) {
int p = -1;
int q = -1;
int min = Integer.MAX_VALUE;
for (int i = 0; i < words.length; i++) {
if (words[i].equals(word1)) {
p = i;
}
if (words[i].equals(word2)) {
q = i;
}
if (p != -1 && q != -1) {
min = Math.min(min, Math.abs(p - q));
}
}
return min;

}
}
```

### Complexity Analysis:

• Time Complexity: O(n).
• Space Complexity: O(1).
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]