Java Solution using HashMap


  • 69
    Q
    public class WordDistance {
    
    private Map<String, List<Integer>> map;
    
    public WordDistance(String[] words) {
        map = new HashMap<String, List<Integer>>();
        for(int i = 0; i < words.length; i++) {
            String w = words[i];
            if(map.containsKey(w)) {
                map.get(w).add(i);
            } else {
                List<Integer> list = new ArrayList<Integer>();
                list.add(i);
                map.put(w, list);
            }
        }
    }
    
    public int shortest(String word1, String word2) {
        List<Integer> list1 = map.get(word1);
        List<Integer> list2 = map.get(word2);
        int ret = Integer.MAX_VALUE;
        for(int i = 0, j = 0; i < list1.size() && j < list2.size(); ) {
            int index1 = list1.get(i), index2 = list2.get(j);
            if(index1 < index2) {
                ret = Math.min(ret, index2 - index1);
                i++;
            } else {
                ret = Math.min(ret, index1 - index2);
                j++;
            }
        }
        return ret;
    }
    }

  • 21

    In shortest( ) function, since list1 (size n) and list2 (size m) are sorted already, we can use the idea of merge sort and perform the comparison in O(n + m) time, rather than O(n * m).


  • 24

    As suggested by @jeantimex in the comments, the function shortest() can be further optimized to be of O(m + n) time. The task here is to find the minimum difference between two sorted lists. And this post has provided a solution :-)

    I solve the problem in C++ :-)

    class WordDistance { 
    public:
        WordDistance(vector<string> words) {
            int n = words.size();
            for (int i = 0; i < n; i++)
                wordInd[words[i]].push_back(i);
        }
    
        int shortest(string word1, string word2) {
            vector<int> indexes1 = wordInd[word1];
            vector<int> indexes2 = wordInd[word2];
            int m = indexes1.size(), n = indexes2.size();
            int i = 0, j = 0, dist = INT_MAX;
            while (i < m && j < n) {
                dist = min(dist, abs(indexes1[i] - indexes2[j]));
                if (indexes1[i] < indexes2[j]) i++;
                else j++;
            }
            return dist;
        }
    private:
        unordered_map<string, vector<int> > wordInd;
    }; 
    

  • 4
    Q

    Thanks, I've updated my solution.


  • 7
    K

    I had a similar idea!

    public class WordDistance {
        HashMap<String,LinkedList<Integer>> map;
        public WordDistance(String[] words) {
            map = new HashMap<String, LinkedList<Integer>>();
            for(int i = 0; i < words.length; i++) {
                String curWord = words[i];
                if(!map.containsKey(curWord)) map.put(curWord,new LinkedList<Integer>());
                map.get(curWord).add(i);
            }
        }
    
        public int shortest(String word1, String word2) {
            int shortest = Integer.MAX_VALUE;
            LinkedList<Integer> word1List = map.get(word1);
            LinkedList<Integer> word2List = map.get(word2);
            int w1Index = 0;
            int w2Index = 0;
            while(w1Index < word1List.size() && w2Index < word2List.size()) {
                int w1 = word1List.get(w1Index);
                int w2 = word2List.get(w2Index);
                shortest = Math.min(shortest, Math.abs(w1-w2));
                if(w1<w2) w1Index++;
                else w2Index++;
            }
            return shortest;
        }
    }

  • 2
    W

    if (ret == 1) break;


  • 0
    D

    Intelligent!


  • 0
    R

    The codes in constructor could be shorter like this:

    public WordDistance(String[] words) {
    map = new HashMap<>();
    for(int i=0;i<words.length;i++)
    map.computeIfAbsent(words[i], list -> new ArrayList<Integer>()).add(i);
    }


  • 0
    C

    @jianchao.li.fighter The code will fail for cases like the following:

    word1Indexes = 10,50,70
    word2Indexes = 22,30,60,71

    The left over portion of the larger length array need to be again checked. In the above cases, the min diff between 70 and 71 will be left out.

    Also the code can be optimized further by binary search;
    Consider the following arrays;
    1,2,3,4,7,9,10
    6,8,11,12

    after the first iteration, diff between word1 and word2 = 6 - 1 = 5

    Hence in array1, no point in looking at values 2,3,4 one by one

    Instead use binary search to find the value in array1 that is larger than the difference of 5 (which is 7).


  • 0
    H

    Two small things;

    map = new HashMap<>();
    
    ret = Math.min(ret, index2 - index1);
    if(index1 < index2) {
        i++;
    } else {
        j++;
    }
    

  • 0
    G

    But if the array only contains two distinct words, then the running time would be O(n), n is the size of the array. Am I right?
    eg: [ "hello","hello","hello","hello","world" ,"world" ,"world" ,"world" ]
    we call shortest("world" , "hello") repeatedly.


  • 1
    W

    I have a question in the solution:map.get(w).add(i); if anyone can answer

    with add method, the above code should return a boolean. I am just wondering why the syntax can ignore the boolean return. Thx!


  • 0
    G

    Same idea, just cleaner code for find shortest distance.

    public int shortest(String word1, String word2) {
        int min = Integer.MAX_VALUE;
        for(Integer num1: map.get(word1)) {
            for(Integer num2: map.get(word2)) {
                min = Math.min(min, Math.abs(num1 - num2));
            }
        }
        return min;
    }

  • 1

    @qianzhige Here's a solution with some additional minor optimizations:

    • Cache the result in the event the same pairs are queried again
    • Bail out immediately once you find that the min diff is 1 since you can never do better than that
    • Cute java8 code that makes setup more terse
    public class WordDistance {
    
        Map<String, List<Integer>> map = new HashMap<>();
        Map<String, Integer> cache = new HashMap<>();
        
        public WordDistance(String[] words) {
            for(int i = 0; i < words.length; i++) {
                map.computeIfAbsent(words[i], v -> new ArrayList<>()).add(i);
            }
        }
        
        public int shortest(String word1, String word2) {
            String key = word1 + "::" + word2;
            if (cache.containsKey(key)) { return cache.get(key); }
            List<Integer> list1 = map.get(word1);
            List<Integer> list2 = map.get(word2);
            int i = 0, j = 0, min = Integer.MAX_VALUE;
            while(i < list1.size() && j < list2.size()) { // pairwise comparison
                int index1 = list1.get(i), index2 = list2.get(j);
                if (index1 > index2) {
                    min = Math.min(min, index1 - index2);
                    j++;
                } else {
                    min = Math.min(min, index2 - index1);
                    i++;                
                }
                if (min == 1) { // doesn't get better than this!
                    cache.put(key, min);
                    return min;
                }
            }
            cache.put(key, min);
            return min;
        }
    }
    

  • 0
    M

    @jianchao.li.fighter nice c++ solution. Maybe declaring indexes1 and indexes2 as references (adding an "&" symbol) can save some space and time (reducing from 42ms to 36ms from my side)


  • 0
    T

    Hi all,

    I have a question for this solution. even though this problem can be solved by this bunch of codes but the asymptomatic time complexity is O(n) for every word1 and word2 pair. Therefore, what's the difference with checking each pair by traveling the whole array?


  • 0
    K

    @qianzhige My solution:

    class WordDistance {
        private Map<String, List<Integer>> map;
        
        public WordDistance(String[] words) {
            map = new HashMap<>();
            for (int i = 0; i < words.length; i ++) {
                String word = words[i];
                List<Integer> list = map.getOrDefault(word, new LinkedList<Integer>());
                list.add(i);
                map.put(word, list);
            }
        }
        
        public int shortest(String word1, String word2) {
            List<Integer> list1 = map.get(word1);
            List<Integer> list2 = map.get(word2);
            
            int min = Integer.MAX_VALUE;
            for (int index1 : list1) {
                for (int index2 : list2) {
                    min = Math.min(min, (int)Math.abs(index1 - index2));
                }
            }
            
            return min;
        }
    }
    

  • 0
    Z

    @TF_boys I had the same question.


  • 0
    W

    How to analyze average time complexity in this problem?


  • 0
    Y

    @TF_boys @WeiWeiJump @zws1818918 If you don't use this method, assuming there are x words in words, then since shortest is called y times, time complexity is O(x * y). This HashMap + mergeSort method will have a time complexity of O(x) + O((m + n) * y), while m and n are the occurrence of word1 and word2 in words. Since m << x and n << x, this is a better method


Log in to reply
 

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