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 * 1041 <= wordsDict[i].length <= 10wordsDict[i] consists of lowercase English letters.word1 and word2 are in wordsDict.word1 != word2- At most
5000 calls will be made to shortest.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class WordDistance:
def __init__(self, wordsDict: List[str]):
self.d = defaultdict(list)
for i, w in enumerate(wordsDict):
self.d[w].append(i)
def shortest(self, word1: str, word2: str) -> int:
a, b = self.d[word1], self.d[word2]
ans = inf
i = j = 0
while i < len(a) and j < len(b):
ans = min(ans, abs(a[i] - b[j]))
if a[i] <= b[j]:
i += 1
else:
j += 1
return ans
# Your WordDistance object will be instantiated and called as such:
# obj = WordDistance(wordsDict)
# param_1 = obj.shortest(word1,word2)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class WordDistance {
private Map<String, List<Integer>> d = new HashMap<>();
public WordDistance(String[] wordsDict) {
for (int i = 0; i < wordsDict.length; ++i) {
d.computeIfAbsent(wordsDict[i], k -> new ArrayList<>()).add(i);
}
}
public int shortest(String word1, String word2) {
List<Integer> a = d.get(word1), b = d.get(word2);
int ans = 0x3f3f3f3f;
int i = 0, j = 0;
while (i < a.size() && j < b.size()) {
ans = Math.min(ans, Math.abs(a.get(i) - b.get(j)));
if (a.get(i) <= b.get(j)) {
++i;
} else {
++j;
}
}
return ans;
}
}
/**
* Your WordDistance object will be instantiated and called as such:
* WordDistance obj = new WordDistance(wordsDict);
* int param_1 = obj.shortest(word1,word2);
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class WordDistance {
public:
WordDistance(vector<string>& wordsDict) {
for (int i = 0; i < wordsDict.size(); ++i) {
d[wordsDict[i]].push_back(i);
}
}
int shortest(string word1, string word2) {
auto a = d[word1], b = d[word2];
int i = 0, j = 0;
int ans = INT_MAX;
while (i < a.size() && j < b.size()) {
ans = min(ans, abs(a[i] - b[j]));
if (a[i] <= b[j]) {
++i;
} else {
++j;
}
}
return ans;
}
private:
unordered_map<string, vector<int>> d;
};
/**
* Your WordDistance object will be instantiated and called as such:
* WordDistance* obj = new WordDistance(wordsDict);
* int param_1 = obj->shortest(word1,word2);
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| type WordDistance struct {
d map[string][]int
}
func Constructor(wordsDict []string) WordDistance {
d := map[string][]int{}
for i, w := range wordsDict {
d[w] = append(d[w], i)
}
return WordDistance{d}
}
func (this *WordDistance) Shortest(word1 string, word2 string) int {
a, b := this.d[word1], this.d[word2]
ans := 0x3f3f3f3f
i, j := 0, 0
for i < len(a) && j < len(b) {
ans = min(ans, abs(a[i]-b[j]))
if a[i] <= b[j] {
i++
} else {
j++
}
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
/**
* Your WordDistance object will be instantiated and called as such:
* obj := Constructor(wordsDict);
* param_1 := obj.Shortest(word1,word2);
*/
|
