L tag
这道题如果按照原题直接写，会tle, 注意到题目中的这个要求：
The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters.
所以如果我们每次有新的input parameters都得重新找index list的话就会很耗时，在words.length很大的时候就会导致超时。所以我们一开始就用map来存下单词和index list的mapping,这样每次call method都可以直接得到index list, 再按照原题的方法做就好了。
class WordDistance {
Map<String, List<Integer>> map;
public WordDistance(String[] words) {
map = new HashMap<>();
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++);
}
}
}
public int shortest(String word1, String word2) {
int shortest = Integer.MAX_VALUE;
int i = 0;
int j = 0;
List<Integer> indexes1 = map.get(word1);
List<Integer> indexes2 = map.get(word2);
while (i < indexes1.size() && j < indexes2.size()){
int dis = 0;
if (indexes1.get(i) > indexes2.get(j)){
dis = indexes1.get(i) - indexes2.get(j);
j++;
} else {
dis = indexes2.get(j) - indexes1.get(i);
i++;
}
shortest = Math.min(dis, shortest);
}
return shortest;
}
}
/**
* Your WordDistance object will be instantiated and called as such:
* WordDistance obj = new WordDistance(words);
* int param_1 = obj.shortest(word1,word2);
*/
