Shortest Word Distance II

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. Your method will be called repeatedly many times with different parameters.

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

Input: word1 = “coding”, word2 = “practice”
Output: 3

Input: word1 = "makes", word2 = "coding"
Output: 1

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

这道题说要重复很多次调用，所以如果简单遍历的话，时间复杂度会很差，那么用hash map，把这个单词每次出现的地方存下来，然后在找到两个单词所有出现位置中的最小差就能找到，时间复杂度为O(MN),但是在遍历两个list的时候可以用two pointer来优化时间复杂度到O(N)

class WordDistance {
    
    
    public String[] words = null;
    
    public HashMap<String,List<Integer>> map = new HashMap<>();
    
    public WordDistance(String[] words) {
        for(int i = 0; i < words.length;i++){
            
            if(map.containsKey(words[i])){
                map.get(words[i]).add(i);
            }else{
                List<Integer> list = new ArrayList<>();
                list.add(i);
                map.put(words[i],list);
            }
        }
    }
    
    public int shortest(String word1, String word2) {
        if(word1 == null || word2 == null || !map.containsKey(word1) || !map.containsKey(word2)){
            return -1;
        }
        
        List<Integer> list1 = map.get(word1);
        List<Integer> list2 = map.get(word2);
        
        int res = Integer.MAX_VALUE;
        
        //for(int i : list1){
        //    for(int j : list2){
        //        res = Math.min(res,Math.abs(i - j));
        //    }
        //}
        
        int i =0, j = 0;
        while(i < list1.size() && j < list2.size()){
            int a = list1.get(i);
            int b = list2.get(j);
            
            res = Math.min(res,Math.abs(a - b));
            
            //找最小距离，所以尽可能缩小a和b的差距
            if(a < b)
                i++;
            if(a > b)
                j++;
        
        }
        
        
        return res;
        
    }
}

/**
 * Your WordDistance object will be instantiated and called as such:
 * WordDistance obj = new WordDistance(words);
 * int param_1 = obj.shortest(word1,word2);
 */

思路：

cz this question require many times calls. It means that if i just go through list every time. It is time consuming. What I am thinking is to record the word's location in the constructor, and everytime to query two word, just get the list of this two word's index and find the min distance.

犯错：res 应该设成int最大数，不然循环内比较时，res永远是0

map，containsKey， k要大写

空间复杂度 o(n),时间复杂度 o(n), query 时间复杂度 o(k),k max number of word1 or word2 numbers

class WordDistance {
    
    
    public Map<String, List<Integer>> map;
    
    public WordDistance(String[] words) {
        this.map = new HashMap<>();
        
        for(int i = 0; i < words.length;i++){
            if(!map.containsKey(words[i])){
                List<Integer> list = new ArrayList<>();
                
                list.add(i);
                map.put(words[i],list);
            }
            
            else{
                map.get(words[i]).add(i);
            }
        }
    }
    
    public int shortest(String word1, String word2) {
        if(!map.containsKey(word1) || !map.containsKey(word2)){
            return -1;
        }
        
        List<Integer> list1 = map.get(word1);
        List<Integer> list2 = map.get(word2);
        
        int res = Integer.MAX_VALUE;
        
        int i = 0, j = 0;
        
        while(i < list1.size() && j < list2.size() ){
            int a = list1.get(i);
            int b = list2.get(j);
            
            res = Math.min(res,Math.abs(a-b));
            
            if(a < b){
                i++;
            }else{
                j++;
            }
            
            
        }
        
        return res;
    }
}

/**
 * Your WordDistance object will be instantiated and called as such:
 * WordDistance obj = new WordDistance(words);
 * int param_1 = obj.shortest(word1,word2);
 */