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 arraywordsDict
.int shortest(String word1, String word2)
returns the shortest distance betweenword1
andword2
in the arraywordsDict
.
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
andword2
are inwordsDict
.word1 != word2
At most
5000
calls will be made toshortest
.
ac
little trick: check map contains key, if not add it. and then add index to the list.
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);
*/
Last updated
Was this helpful?