Clean and concise Java solution. O(n) time


  • 5
    V

    The idea is pretty simple. Memorizing all the positions that each string appears. Put it into a array and store <String, List<Integer>> as a pair in the hash map. When we need to find the shortest path of two string, just get the two list of these two string. Use two pointers and scan the two lists at the same time. When any pointer reach the end. Stop the loop. When we found out that the first position is greater than the second one. We add one to the second pointer. Else, add to the first pointer. This idea is like always keep minimum difference between the two position and move the two pointers.

    Map<String, List<Integer>> map;
    public WordDistance(String[] words) {
        map=new HashMap<String, List<Integer>>();
        for(int i=0; i<words.length; i++){
            String temp=words[i];
            if(map.containsKey(temp)){
                map.get(temp).add(i);
            }else{
                List<Integer> list=new ArrayList<Integer>();
                list.add(i);
                map.put(temp, list);
            }
        }
    }
    
    public int shortest(String word1, String word2) {
        int min=Integer.MAX_VALUE;
        List<Integer> list1=map.get(word1);
        List<Integer> list2=map.get(word2);
        int size1=list1.size(), size2=list2.size();
        int i=0, j=0;
        while(i< size1 && j<size2){
            int t1=list1.get(i), t2=list2.get(j);
            if(t1<t2){
                min=Math.min(min, t2-t1);
                i++;
            }else{
                min=Math.min(min, t1-t2);
                j++;
            }
        }                                
        return min;     
    }

  • 0
    F

    The worst case is when half of the elements are the same, so scanning (n/2)*(n/2) is o(n^2), correct?


  • 0
    K

    @floyo I think it is O(K + L) where K is the number of word1s and L is the number of word2s


  • 2

    Since the problem stated that the shortest distance call will be called repeatedly, so once a such call with parameters (word1, word2) is made with O(N) cost for the first time, it is better not to cost O(N) again if a second call with same inputs are made.

    Instead, define a map with pair<string, string> as key in the class. Whenever a call with inputs (word1, word2) is made (swap words to make sure word1 < word2 for uniqueness purpose), if this pair is already registered, find its value and return directly; otherwise, compute as you did and register its value before return. So we do not compute twice for the same inputs.

    Another way is to generate the entire hash map with key type pair<string, string> in constructor O(N^2), then each call of shortest will be simply O(1).

    For this specific problem, I do think we should sacrifice space for time.


Log in to reply
 

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