Solution URL
https://leetcode.com/submissions/detail/420198500/
代码
class WordDistance {
//ans: Solution
//Time: O(N)
//Space: O(N)
//store words and corresponding indexes
Map<String, List<Integer>> dict = new HashMap<>();
public WordDistance(String[] words) {
this.dict = dict;
//iterate the array of words and store the index
for(int i = 0; i < words.length; i++){
//get the index list according to the word
List<Integer> loc = this.dict.getOrDefault(words[i], new ArrayList<>());
//add the index into the list
loc.add(i);
//put the updated loc list into the map
dict.put(words[i], loc);
}
}
public int shortest(String word1, String word2) {
//get the list of indexes of the two words
List<Integer> list1 = dict.get(word1);
List<Integer> list2 = dict.get(word2);
//iterate the two list to get the min distance
int i = 0;
int j = 0;
int minDis = Integer.MAX_VALUE;
while(i < list1.size() && j < list2.size()){
int idx1 = list1.get(i);
int idx2 = list2.get(j);
if(idx1 < idx2){
i++;
}else{
j++;
}
minDis = Math.min(minDis, Math.abs(idx1 - idx2));
}
return minDis;
}
}
/**
* Your WordDistance object will be instantiated and called as such:
* WordDistance obj = new WordDistance(words);
* int param_1 = obj.shortest(word1,word2);
*/
