Java Solution using HashMap.


  • 0
    I
    HashMap<String,List<Integer>> map = new HashMap<String,List<Integer>>(); 
    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> indexList = new ArrayList<Integer>();
                indexList.add(i);
                map.put(words[i],indexList);
            }
        }
    }
    
    public int shortest(String word1, String word2) {
        List<Integer> index1 = map.get(word1);
        List<Integer> index2 = map.get(word2);
        int min = Integer.MAX_VALUE;
        for(int i : index1) {
            for (int j : index2) {
                min = Math.min(min, Math.abs(i - j));
            }
        }
        return min;
    }

  • 3
    Y
    public int shortest(String word1, String word2) {
            LinkedList<Integer> list1 = map.get(word1);
            LinkedList<Integer> list2 = map.get(word2);
            int index1 = 0;
            int index2 = 0;
            int min = Integer.MAX_VALUE;
            while(index1 < list1.size() && index2 < list2.size()){
                min = Math.min(min, Math.abs(list1.get(index1) - list2.get(index2)));
                if(list1.get(index1) < list2.get(index2)){
                    index1++;
                } else {
                    index2++;
                }
            }
            return min;
        }
    

    This will reduce the find shortest from O(N^2) to O(N);


Log in to reply
 

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