# 0244. Shortest Word Distance II

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

## Description

Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array.

Implement the `WordDistance` class:

* `WordDistance(String[] wordsDict)` initializes the object with the strings array `wordsDict`.
* `int shortest(String word1, String word2)` returns the shortest distance between `word1` and `word2` in the array `wordsDict`.

**Example 1:**

```
**Input**
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
**Output**
[null, 3, 1]
**Explanation**
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // return 3
wordDistance.shortest("makes", "coding");    // return 1
```

**Constraints:**

* `1 <= wordsDict.length <= 3 * 104`
* `1 <= wordsDict[i].length <= 10`
* `wordsDict[i]` consists of lowercase English letters.
* `word1` and `word2` are in `wordsDict`.
* `word1 != word2`
* At most `5000` calls will be made to `shortest`.

## ac

little trick: check map contains key, if not add it. and then add index to the list.

```java
class WordDistance {
    Map<String, List<Integer>> map;
    public WordDistance(String[] words) {
        map = new HashMap<String, List<Integer>>();
        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> l1 = map.get(word1);
        List<Integer> l2 = map.get(word2);
        int diff = Integer.MAX_VALUE;

        for (int i : l1) {
            for (int j : l2) {
                diff = Math.min(diff, Math.abs(i-j));
            }
        }

        return diff;
    }
}

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