244. Shortest Word Distance II

LeetCode 244. 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

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: 二分法找到最接近的索引