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


---

# 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://txfs19260817.gitbook.io/leetcode-go-notes/solutions/244.-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.