Solution URL
https://leetcode.com/submissions/detail/420526530/
代码
class Solution {
//ans: modify according to Pro244
//Time: O(N)
//Space: O(N)
int minDis = Integer.MAX_VALUE;
public int shortestWordDistance(String[] words, String word1, String word2) {
//use map to store all words and corresponding indexes
Map<String, List<Integer>> map = new HashMap<>();
for(int i = 0; i < words.length; i++){
//get the list of index
List<Integer> list = map.getOrDefault(words[i], new ArrayList<>());
//put the index into the list
list.add(i);
//update map
map.put(words[i], list);
}
//get the lists of two words and calculate the shortest distance between them
if(word1.equals(word2)){//if not the same word
List<Integer> l1 = map.get(word1);
//loop the list
int dis = 0;
for(int i = 1; i < l1.size(); i++){
dis = l1.get(i) - l1.get(i - 1);
minDis = Math.min(dis, minDis);
}
}else{//if the same word
List<Integer> l1 = map.get(word1);
List<Integer> l2 = map.get(word2);
//calculate the shortest distance
minDis = calDis(l1, l2);
}
return minDis;
}
private int calDis(List<Integer> l1, List<Integer> l2){
//loop the two lists
int i = 0;
int j = 0;
while(i < l1.size() && j < l2.size()){
int dis = Math.abs(l2.get(j) - l1.get(i));
if(l1.get(i) < l2.get(j)){
i++;
}else{
j++;
}
minDis = Math.min(minDis, dis);
}
return minDis;
}
}
