Monday, August 24, 2015

Leetcode: 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.
Understand the problem:
The problem is almost the same as the previous one. The only diff is the method will be called multiple times. The native solution is to reset the posA, posB and minDistance each time the method being called. 

Code (Java):
public class WordDistance {
    private String[] words;
    int posA;
    int posB;
    int minDistance;
    
    private void reset() {
        posA = -1;
        posB = -1;
        minDistance = Integer.MAX_VALUE;
    }
    
    public WordDistance(String[] words) {
        this.words = words;
        reset();
    }

    public int shortest(String word1, String word2) {
        reset();
        
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            if (word.equals(word1)) {
                posA = i;
            }
            
            if (word.equals(word2)) {
                posB = i;
            }
            
            if (posA != -1 && posB != -1) {
                minDistance = Math.min(minDistance, Math.abs(posA - posB));
            }
        }
        
        return minDistance;
    }
}
// Your WordDistance object will be instantiated and called as such:
// WordDistance wordDistance = new WordDistance(words);
// wordDistance.shortest("word1", "word2");
// wordDistance.shortest("anotherWord1", "anotherWord2");

The solution is correct. But will cause time-limit exceed error. 
Let's rethink about the problem again. If the method is called multiple times, each time it will need to iterate over the array once. However, if we can put the words into a hash map, we don't have to iterate over the array again and again. It is only a one time cost. 

Solution using a hash map:
public class WordDistance {
    private Map<String, List<Integer>> map = new HashMap<String, List<Integer>>();
    
    
    public WordDistance(String[] words) {
        fill(words);
    }
    
    private void fill(String[] words) {
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            if (map.containsKey(word)) {
                List<Integer> pos = map.get(word);
                pos.add(i);
                map.put(word, pos);
            } else {
                List<Integer> pos = new ArrayList<Integer>();
                pos.add(i);
                map.put(word, pos);
            }
        }
    }

    public int shortest(String word1, String word2) {
        int minDistance = Integer.MAX_VALUE;
        
        List<Integer> posA = map.get(word1);
        List<Integer> posB = map.get(word2);
        
        for (int i : posA) {
            for (int j : posB) {
                minDistance = Math.min(minDistance, Math.abs(i - j));
            }
        }
        
        return minDistance;
    }
}

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

Better approach to calculate the shortest distance:
Since the index in each list is in sorted order. We may use this property to calculate the shortest distance in O(m + n) instead of O(m * n)

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

    public int shortest(String word1, String word2) {
        List<Integer> pos1 = map.get(word1);
        List<Integer> pos2 = map.get(word2);
        
        int minDistance = Integer.MAX_VALUE;
        int i = 0;
        int j = 0;
        while (i < pos1.size() && j < pos2.size()) {
            int p1 = pos1.get(i);
            int p2 = pos2.get(j);
            if (p1 < p2) {
                minDistance = Math.min(minDistance, p2 - p1);
                i++;
            } else {
                minDistance = Math.min(minDistance, p1 - p2);
                j++;
            }
        }
        
        return minDistance;
    }
}

No comments:

Post a Comment