244. Shortest Word Distance II

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.

public class WordDistance {
    Map<String, TreeSet<Integer>> map = new HashMap<>();
    public WordDistance(String[] words) {
        for(int i =0; i< words.length; i++){
            TreeSet<Integer> ts;
            if(map.containsKey(words[i])){
                ts = map.get(words[i]);
            }else{
                ts = new TreeSet<Integer>();
                map.put(words[i], ts);
            }
            ts.add(i);
        }
    }

    public int shortest(String word1, String word2) {
        TreeSet<Integer> ts1 = map.get(word1);
        TreeSet<Integer> ts2 = map.get(word2);
        int s = Integer.MAX_VALUE;
        for(Integer i : ts1){
            Integer f = ts2.floor(i);
            if(f != null) s = Math.min(s, i - f);
            Integer h = ts2.higher(i);
            if(h != null) s = Math.min(s, h - i);
        }
        return s;
    }
}

// Your WordDistance object will be instantiated and called as such:
// WordDistance wordDistance = new WordDistance(words);
// wordDistance.shortest("word1", "word2");
// wordDistance.shortest("anotherWord1", "anotherWord2");

O(n) solution, you can look into the arrays more carefully you only need to compare each one at a time, and move the smaller pointer ahead.

To further step improve the performance, if you have a string only show up once, then you can use above solution to achieve a log(k) solution.

public class WordDistance {
    Map<String, List<Integer>> map = new HashMap<>();
    public WordDistance(String[] words) {
        for(int i =0; i< words.length; i++){
            List<Integer> ts;
            if(map.containsKey(words[i])){
                ts = map.get(words[i]);
            }else{
                ts = new ArrayList<Integer>();
                map.put(words[i], ts);
            }
            ts.add(i);
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> ts1 = map.get(word1);
        List<Integer> ts2 = map.get(word2);
        int s = Integer.MAX_VALUE;
        int i = 0;
        int k = 0;
        while(i < ts1.size() && k < ts2.size()){
            s = Math.min(s, Math.abs(ts1.get(i) - ts2.get(k)));
            if(ts1.get(i) > ts2.get(k)){
                k++;
            }else{
                i++;
            }
        }

        return s;
    }
}

// Your WordDistance object will be instantiated and called as such:
// WordDistance wordDistance = new WordDistance(words);
// wordDistance.shortest("word1", "word2");
// wordDistance.shortest("anotherWord1", "anotherWord2");