Shortest Word Distance II

Design, Hash Map

Medium

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. Your method will be called _repeatedly _many times with different parameters.

Example: Assume that words =["practice", "makes", "perfect", "coding", "makes"].

Input:
word1
 = 
“coding”
, 
word2
 = 
“practice”
Output:
 3

Input:
word1
 = 
"makes"
, 
word2
 = 
"coding"
Output:
 1

Note: You may assume thatword1 does not equal to word2, and _word1 _and _word2 _are both in the list.

Analysis

顺序遍历words[]，把对应index放入hashmap中<String, ArrayList<Integer>>；这样每个word对应的index其实是默认按照升序排好序了。

shortest()在计算时，brute-force就是两重循环找min。但是更聪明的办法是用two pointers，分别在两个sorted list中，最小的绝对值之差就可以通过一重循环找到了。

[3,4,10,11]
[1,6,12]

list1.get(i1) < list2.get(i2) 则增加i1，否则增加i2

Solution

Location mapping, and brute force two nested for loops

• shortest() takes O(pq) time

class WordDistance {
    private HashMap<String, ArrayList<Integer>> map;

    public WordDistance(String[] words) {
        map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            if (!map.containsKey(words[i])) {
                map.put(words[i], new ArrayList<Integer>());
            }
            map.get(words[i]).add(i);
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> p1 = map.get(word1);
        List<Integer> p2 = map.get(word2);
        if (p1 == null || p2 == null) {
            return -1;
        }
        int shortest = Integer.MAX_VALUE;
        for (Integer i1: p1) {
            for (Integer i2: p2) {
                shortest = Math.min(Math.abs(i1 - i2), shortest);
            }
        }
        return shortest;
    }
}

/**
 * Your WordDistance object will be instantiated and called as such:
 * WordDistance obj = new WordDistance(words);
 * int param_1 = obj.shortest(word1,word2);
 */

Optimized - using two pointers

• shortest() takes O(p + q) time

class WordDistance {
    private HashMap<String, ArrayList<Integer>> map;

    public WordDistance(String[] words) {
        map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            if (!map.containsKey(words[i])) {
                map.put(words[i], new ArrayList<Integer>());
            }
            map.get(words[i]).add(i);
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> p1 = map.get(word1);
        List<Integer> p2 = map.get(word2);
        if (p1 == null || p2 == null) {
            return -1;
        }
        int shortest = Integer.MAX_VALUE;
        int i1 = 0;
        int i2 = 0;
        while (i1 < p1.size() && i2 < p2.size()) {
            shortest = Math.min(Math.abs(p1.get(i1) - p2.get(i2)), shortest);
            if (p1.get(i1) < p2.get(i2)) {
                i1++;
            } else {
                i2++;
            }
        }
        return shortest;
    }
}

/**
 * Your WordDistance object will be instantiated and called as such:
 * WordDistance obj = new WordDistance(words);
 * int param_1 = obj.shortest(word1,word2);
 */

Reference

https://leetcode.com/problems/shortest-word-distance-ii/solution/