Problem

Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array.

Implement the WordDistance class:

  • WordDistance(String[] wordsDict) initializes the object with the strings array wordsDict.
  • int shortest(String word1, String word2) returns the shortest distance between word1 and word2 in the array wordsDict.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]

Output
[null, 3, 1]

Explanation
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // return 3
wordDistance.shortest("makes", "coding");    // return 1

Solution

Method 1 - Using Hashtable

The goal is to design a class that pre-processes the list of words to efficiently answer multiple queries about the shortest distance between two words.

  1. Pre-processing:
    • Create a hash table to store the positions of each word in the array.
    • This facilitates quick lookups and distance calculations.
  2. Calculating Distance:
    • For queries, retrieve the lists of positions for both words from the hash table.
    • Use two pointers to iterate through these lists and find the minimum distance between the positions.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public class WordDistance {
    private Map<String, List<Integer>> positions;

    public WordDistance(String[] wordsDict) {
        positions = new HashMap<>();
        for (int i = 0; i < wordsDict.length; ++i) {
            positions.computeIfAbsent(wordsDict[i], k -> new ArrayList<>()).add(i);
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> pos1 = positions.get(word1);
        List<Integer> pos2 = positions.get(word2);
        int ans = Integer.MAX_VALUE;
        int i = 0, j = 0;
        while (i < pos1.size() && j < pos2.size()) {
            ans = Math.min(ans, Math.abs(pos1.get(i) - pos2.get(j)));
            if (pos1.get(i) < pos2.get(j)) {
                i++;
            } else {
                j++;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class WordDistance:
    def __init__(self, wordsDict: List[str]) -> None:
        self.positions: Dict[str, List[int]] = defaultdict(list)
        for index, word in enumerate(wordsDict):
            self.positions[word].append(index)
    
    def shortest(self, word1: str, word2: str) -> int:
        pos1 = self.positions[word1]
        pos2 = self.positions[word2]
        i, j = 0, 0
        ans = float('inf')
        
        while i < len(pos1) and j < len(pos2):
            ans = min(ans, abs(pos1[i] - pos2[j]))
            if pos1[i] < pos2[j]:
                i += 1
            else:
                j += 1
                
        return ans

Complexity

  • ⏰ Time complexity:
    • Pre-processing: O(n) since we only need to iterate through the list of words once.
    • Query: O(m + k) where m is the length of the positions list for word1 and k is the length of the positions list for word2.
  • 🧺 Space complexity:
    • Pre-processing: O(n) to store the positions of each word.