Medium
題邏輯很簡單费封，為了完成O(M*N)到O(M + N)的optimization, 需要用到類似于mergesort的比較方法，能夠用到的原因是因為我們兩個list本來就是sorted的
class WordDistance {
Map<String, List<Integer>> map;
public WordDistance(String[] words) {
map = new HashMap<String, List<Integer>>();
int index = 0;
for (String word : words){
if (!map.containsKey(word)){
map.put(word, new ArrayList<Integer>(Arrays.asList(index++)));
} else {
map.get(word).add(index++);
}
}
}
// ["WordDistance","shortest","shortest"]
// [[["a","a","b","b"]],["a","b"],["b","a"]]
public int shortest(String word1, String word2) {
List<Integer> indexes1 = map.get(word1);
List<Integer> indexes2 = map.get(word2);
int shortest = Integer.MAX_VALUE;
for (int i = 0, j = 0; i < indexes1.size() && j < indexes2.size();){
int index1 = indexes1.get(i);
int index2 = indexes2.get(j);
if (index1 < index2){
shortest = Math.min(index2 - index1, shortest);
i++;
} else {
shortest = Math.min(index1 - index2, shortest);
j++;
}
}
return shortest;
}
}
/**
* Your WordDistance object will be instantiated and called as such:
* WordDistance obj = new WordDistance(words);
* int param_1 = obj.shortest(word1,word2);
*/
