Problem Source: LeetCode
Companies: LinkedIn, Microsoft, Paypal, Oracle.
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).
