Clear Java solution using HashMap


  • 0

    O(n) for building dictionary. O(n) for calculating word distance.
    Same code ran 3 times. All AC'ed.
    But 1st time beat 82.3%, 2nd beat 76%, and 3rd time 40%.
    Probably, runtime performance also depends on workload at the moment.

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

    Note:
    For the shortest method, I tried the approach at first, but got TLE.
    https://discuss.leetcode.com/topic/20668/ac-java-clean-solution
    In the light, using for loop to traverse all possible indices is time consuming.

        public int shortest(String word1, String word2) {
            List<Integer> list1 = map.get(word1);  
            List<Integer> list2 = map.get(word2); 
            int ind1 = -1, ind2 = -1, shortest = Integer.MAX_VALUE; 
            int min = Math.min(list1.get(0), list2.get(0)); 
            int max = Math.max(list1.get(list1.size() - 1), list2.get(list2.size() - 1)); 
    
            for (int i = min; i <= max; i++) {
                if (list1.contains(i)) ind1 = i; 
                if (list2.contains(i)) ind2 = i; 
                if ((ind1 == i || ind2 == i) && (ind1 != -1 && ind2 != -1)) 
                    shortest = Math.min(shortest, Math.abs(ind2 - ind1)); 
            }
            
            return shortest; 
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.