Shortest Word Distance II

Design, Hash Map

Medium

Design a class which receives a list of words in the constructor, and implements a method that takes two words _word1 _and _word2 _and return the shortest distance between these two words in the list. Your method will be called _repeatedly _many times with different parameters.

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

Input:
word1
=
“coding”
,
word2
=
“practice”
Output:
3
Input:
word1
=
"makes"
,
word2
=
"coding"
Output:
1

Note:
You may assume thatword1 does not equal to word2, and _word1 _and _word2 _are both in the list.

Analysis

shortest()在计算时，brute-force就是两重循环找min。但是更聪明的办法是用two pointers，分别在两个sorted list中，最小的绝对值之差就可以通过一重循环找到了。

[3,4,10,11]
[1,6,12]
list1.get(i1) < list2.get(i2) 则增加i1，否则增加i2

Solution

Location mapping, and brute force two nested for loops

• shortest() takes O(pq) time
class WordDistance {
private HashMap<String, ArrayList<Integer>> map;

public WordDistance(String[] words) {
map = new HashMap<>();
for (int i = 0; i < words.length; i++) {
if (!map.containsKey(words[i])) {
map.put(words[i], new ArrayList<Integer>());
}
}
}

public int shortest(String word1, String word2) {
List<Integer> p1 = map.get(word1);
List<Integer> p2 = map.get(word2);
if (p1 == null || p2 == null) {
return -1;
}
int shortest = Integer.MAX_VALUE;
for (Integer i1: p1) {
for (Integer i2: p2) {
shortest = Math.min(Math.abs(i1 - i2), shortest);
}
}
return shortest;
}
}

/**
* Your WordDistance object will be instantiated and called as such:
* WordDistance obj = new WordDistance(words);
* int param_1 = obj.shortest(word1,word2);
*/

Optimized - using two pointers

• shortest() takes O(p + q) time
class WordDistance {
private HashMap<String, ArrayList<Integer>> map;

public WordDistance(String[] words) {
map = new HashMap<>();
for (int i = 0; i < words.length; i++) {
if (!map.containsKey(words[i])) {
map.put(words[i], new ArrayList<Integer>());
}
}
}

public int shortest(String word1, String word2) {
List<Integer> p1 = map.get(word1);
List<Integer> p2 = map.get(word2);
if (p1 == null || p2 == null) {
return -1;
}
int shortest = Integer.MAX_VALUE;
int i1 = 0;
int i2 = 0;
while (i1 < p1.size() && i2 < p2.size()) {
shortest = Math.min(Math.abs(p1.get(i1) - p2.get(i2)), shortest);
if (p1.get(i1) < p2.get(i2)) {
i1++;
} else {
i2++;
}
}
return shortest;
}
}

/**
* Your WordDistance object will be instantiated and called as such:
* WordDistance obj = new WordDistance(words);
* int param_1 = obj.shortest(word1,word2);
*/

Reference

https://leetcode.com/problems/shortest-word-distance-ii/solution/