244. Shortest Word Distance II (1)

Link

This is a follow up of Shortest Word Distance. 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.

Solution

Use a hashmap to record the list of indexs for each word

whenever we query, just focus on handle the list of word1 and word2.

And find the min difference of value in the two lists

值得注意的點是，map中的value是每個word出現的indexes，而且已經由小到大排列好了，找尋indexes間的差值最小的方法，就是iterate兩個list，計算最小差值，然後把比較小的index+1，看看能不能更小。以這種方法找出min

public class ShortestPath {
    private HashMap<String, ArrayList<Integer>> maps = new HashMap<>();
    public ShortestPath(String[] words){
        for (int i = 0 ; i < words.length ; i++) {
            String word = words[i];
            if(!maps.containsKey(word)){
                maps.put(word, new ArrayList<Integer>());
            }
            maps.get(word).add(i);
        }
    }
    public int getShortestDistance(String word1, String word2){
        ArrayList<Integer> list1 = maps.get(word1);
        ArrayList<Integer> list2 = maps.get(word2);
        int i = 0, j = 0, min = Integer.MAX_VALUE;
        while (i < list1.size() && j < list2.size()){
            if(list1.get(i) > list2.get(j))
            {
                min = Math.min(min, list1.get(i) - list2.get(j));
                j++;
            }
            else if (list1.get(i) < list2.get(j)){
                min = Math.min(min, list1.get(j) - list2.get(i));
                i++;
            }
        }
        return min;
    }
}