> For the complete documentation index, see [llms.txt](https://txfs19260817.gitbook.io/leetcode-go-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/244.-shortest-word-distance-ii.md).

# 244. Shortest Word Distance II

## LeetCode [244. Shortest Word Distance II](https://leetcode-cn.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 * 10^4`
* `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`.

### Tags

Design, Hash Table, Binary Search

### Solution

Build a hash table mapping from word to its indices list. For faster distance search, we perform binary search on one of the lists.

### Complexity

* Time complexity: $$O(\max(len(l1), len(l2)))$$
* Space complexity: $$O(n)$$

### Code

```go
type WordDistance struct {
	word2indices map[string][]int
}

func Constructor(wordsDict []string) WordDistance {
	word2indices := make(map[string][]int)
	for i, s := range wordsDict {
		word2indices[s] = append(word2indices[s], i)
	}
	return WordDistance{word2indices}
}

func (this *WordDistance) Shortest(word1 string, word2 string) int {
	l1, l2 := this.word2indices[word1], this.word2indices[word2]
	ans := abs(l1[0] - l2[0])
	for _, i := range l1 {
		switch j := sort.SearchInts(l2, i); j {
		case 0:
			ans = min(ans, abs(i-l2[0]))
		case len(l2):
			ans = min(ans, abs(i-l2[len(l2)-1]))
		default:
			ans = min(ans, min(abs(l2[j]-i), abs(l2[j-1]-i)))
		}
	}
	return ans
}

func abs(a int) int {
	if a < 0 {
		return -1 * a
	}
	return a
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
```

## Reference

1. [Python: 二分法找到最接近的索引](https://leetcode-cn.com/problems/shortest-word-distance-ii/solution/python-er-fen-fa-zhao-dao-zui-jie-jin-de-offa/)