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);
 */