LeetCode 244. Shortest Word Distance II

Problem Clarification

Design a class that:

1. receives a list of words (may contain duplicates) in the constructor
2. called repeatedly with word1 and word2 (the two words do not equal to each other, and they are both in the list) and return the shortest word distance

Shortest word distance definition: minimum absolute gap between the indices of the two words in the list

e.g. words = [“practice”, “makes”, “perfect”, “coding”, “makes”]

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

Analysis

Principle: Choose efficient data structure for memorizing the list of words, to enable fast inquiries.

• raw (list): When called, sequentially scan for word1 and word2, continuously update largest indices and calculate the index distance.

  Time complexity $\Theta(N)$, space complexity $O(1)$

• index dictionary: Preprocess to get sorted indices. When called, retrieve for the indexes directly (list length K and L), then loop through the indexes to find the minimum difference.

  Time complexity $O(K+L)$ ~ $O(N)$, space complexity $O(N)$

Another point: when calculate index difference between two list, use two pointers $O(N)$ rather than brute-force all index pairs $O(N^2)$.

Code

I found my runtime only ranked ~60% (not much different from code samples of high ranks), and the implemention nuances (update min_diff in if statement or in math.abs; whether assign list lengths to variables before while loop) have mysterious effects.

• Python

from collections import defaultdict

class WordDistance:

    def __init__(self, words):
        self.log = defaultdict(list)
        for loc, word in enumerate(words):
            self.log[word].append(loc)
        
    def shortest(self, word1, word2):
        locs1, locs2 = self.log[word1], self.log[word2]
        i, j = 0, 0
        m, n = len(locs1), len(locs2)
        
        min_diff = float('inf')
        
        while i < m and j < n:
            min_diff = min(min_diff, abs(locs1[i] - locs2[j]))
            if min_diff == 1:
                break
            if locs1[i] < locs2[j]:
                i += 1
            else:
                j += 1
            
        return min_diff

• Java

class WordDistance {
    private Map<String, List<Integer>> locations;
    
    public WordDistance(String[] words) {
        locations = new HashMap<String, List<Integer>>();
        for(int i = 0; i < words.length; i++) {
            String word = words[i];
            if(locations.containsKey(word)) {
                locations.get(word).add(i);
            } else {
                List lst = new ArrayList<Integer>();
                lst.add(i);
                locations.put(word, lst);
            }
        }
    }
    
    public int shortest(String word1, String word2) {
        List<Integer> lst1 = locations.get(word1);
        List<Integer> lst2 = locations.get(word2);
        int minDiff = Integer.MAX_VALUE;
        for(int i = 0, j = 0; i < lst1.size() && j < lst2.size(); ) {
            int loc1 = lst1.get(i), loc2 = lst2.get(j);
            if(loc1 < loc2) {
                minDiff = Math.min(minDiff, loc2 - loc1);
                i++;
            } else {
                minDiff = Math.min(minDiff, loc1 - loc2);
                j++;
            }
            if (minDiff == 1) {
                return minDiff;
            }
        }
        return minDiff;
    }
}