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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/hash-table/shortest-word-distance-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.