# 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 that*word1* **does not equal to** *word2*, and \_word1 \_and \_word2 \_are both in the list.

## Analysis

顺序遍历words\[]，把对应index放入hashmap中\<String, ArrayList\<Integer>>；这样每个word对应的index其实是默认按照升序排好序了。

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

```java
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>());
            }
            map.get(words[i]).add(i);
        }
    }

    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

```java
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>());
            }
            map.get(words[i]).add(i);
        }
    }

    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/>