原题链接在这里：

题目：

This is a follow up of . The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

For example,

Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”, word2 = “practice”, return 3.

Given word1 = "makes", word2 = "coding", return 1.

题解：

类似.

method 会被call好多次，没有必要每次都traverse 一遍words array. 简历一个HashMap, key是word, value是该word出现index的list.

双指针遍历word1 和 word2 两个index list 计算最小距离.

Time Complexity: Constructor WordDistance O(words.length). shortest O(list1.size()+list2.size()).

Space: O(1) regardless HashMap.

AC Java:

1 public class WordDistance { 2  3     HashMap
     
      > hm; 4     public WordDistance(String[] words) { 5         hm = new HashMap
      
       >(); 6         for(int i = 0; i
       
         ls = new ArrayList
        
         (); 9                 hm.put(words[i], ls);10             }11             hm.get(words[i]).add(i);12         }13     }14 15     public int shortest(String word1, String word2) {16         List
         
           l1 = hm.get(word1);17         List
          
            l2 = hm.get(word2);18 int res = Integer.MAX_VALUE;19 int i = 0;20 int j = 0;21 while(i
          
         
        
       
      
     

跟上.