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.

Note:

You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

 

1. 建立和遍历时间复杂度都是O(n)的解法。比之前的方法的优化点是取两个下标list来获得两者pair的差的最小值的求法。现在改为用两个指针各指着某一个下标，之后哪个指着的下标是小一点的，就挪哪一个指针。这样总能保证每次尽量让两个下标靠的最近，最后打擂台出来的肯定能打到最小值。

2.初始化建完全映射的一个解法，建立的时候时间复杂度是O(n4)，但是之后取的是O(1)，问要不要这个权衡吧。

用的数据结构是map<String, List<Integer>>(映射字符串和它的下标)，以及int[i][j](记录words[i]和words[j]之间的距离)。

这样之后调用的时候只要读一次map以及读一次array就好。

1.O(n), O(n)

class WordDistance {    private Map
     
      > map;        public WordDistance(String[] words) {        map = new HashMap
      
       >();        for (int i = 0; i < words.length; i++) {            if (!map.containsKey(words[i])) {                map.put(words[i], new ArrayList
       
        ());            }            map.get(words[i]).add(i);        }    }        public int shortest(String word1, String word2) {        List
        
          l1 = map.get(word1);        List
         
           l2 = map.get(word2);                int p1 = 0, p2 = 0;        int min = Integer.MAX_VALUE;        while (p1 < l1.size() && p2 < l2.size()) {            min = Math.min(min, Math.abs(l1.get(p1) - l2.get(p2)));            if (l1.get(p1) <= l2.get(p2)) {                p1++;            } else {                p2++;            }        }        return min;    }}/** * Your WordDistance object will be instantiated and called as such: * WordDistance obj = new WordDistance(words); * int param_1 = obj.shortest(word1,word2); */
         
        
       
      
     

 

 

2. O(n4), O(1)

class WordDistance {    private int[][] dist;    private Map
     
      > map;        public WordDistance(String[] words) {                dist = new int[words.length][words.length];        map = new HashMap
      
       >();                for (int i = 0; i < words.length; i++) {            if (!map.containsKey(words[i])) {                map.put(words[i], new ArrayList
       
        ());            }             map.get(words[i]).add(i);        }                for (int i = 0; i < words.length; i++) {            for (int j = 0; j < words.length; j++) {                dist[i][j] = -1;            }        }        for (int i = 0; i < words.length; i++) {            for (int j = 0; j < words.length; j++) {                if (dist[i][j] != -1) {                    continue;                }                List
        
          idxs1 = map.get(words[i]);                List
         
           idxs2 = map.get(words[j]);                int min = Integer.MAX_VALUE;                for (int m = 0; m < idxs1.size(); m++) {                    for (int n = 0; n < idxs2.size(); n++) {                        min = Math.min(min, Math.abs(idxs1.get(m) - idxs2.get(n)));                    }                }                for (int m = 0; m < idxs1.size(); m++) {                    for (int n = 0; n < idxs2.size(); n++) {                        dist[idxs1.get(m)][idxs2.get(n)] = min;                        dist[idxs2.get(n)][idxs1.get(m)] = min;                    }                }                            }        }     }        public int shortest(String word1, String word2) {        return dist[map.get(word1).get(0)][map.get(word2).get(0)];    }}/** * Your WordDistance object will be instantiated and called as such: * WordDistance obj = new WordDistance(words); * int param_1 = obj.shortest(word1,word2); */