244. Shortest Word Distance II

244 is for huge data size, 243 is for small data size

Solution1:

compare two lists, one by one => time: O(n^2)

Solution2:

use two pointer => O(n + m)

because the map<String, List<Integer>>, the list adds by order and not repeated,

the shortest distance happened at two list's closest index

ex:

i

j

[ 1(a3), 2(a4), 3(a4), 6(a3), 8(a4) ]

when a[i] < a[j] we should i++ .=> to find next min . (not move j, that's will increase the distance , right?)

i

j

[ 1(a3), 2(a4), 3(a4), 6(a3), 8(a4) ]

until ending

time: O(n), n is the wordsDict's length

space: O(n)

class WordDistance {

    private Map<String, List<Integer>> map = new HashMap<>();
    public WordDistance(String[] wordsDict) {
        for (int i = 0; i < wordsDict.length ; i++) {
            String w = wordsDict[i];
            List<Integer> data = map.getOrDefault(w, new ArrayList<>());
            data.add(i);
            map.put(w, data);
        }
    }
    
    public int shortest(String word1, String word2) {
        List<Integer> data1 = map.get(word1);
        List<Integer> data2 = map.get(word2);
        
        int i = 0, j = 0;
        int min = Integer.MAX_VALUE;
        while (i < data1.size() && j < data2.size()) {
            min = Math.min(min, Math.abs(data1.get(i) - data2.get(j)));
            
            if (data1.get(i) > data2.get(j)) {
                j++;
            } else {
                i++;
            }
        }
        return min;
    }
}

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

Solution 3:

in two lists, for loop and use binary search

time: O(m * logn)

space: O(n)