Problem Explanation

In numerous situations, particularly in activities such as information retrieval, we often want to find the distance between two words in a document. This problem involves designing a class that can do just that. We want to create a class capable to receive a list of words and implement a method that can calculate the shortest distance between any two specified words in the document.

Example

Let's consider an example:

If we have an array of words like ["practice", "makes", "perfect", "coding", "makes"]. To find the distance between "coding" and "practice", we could iterate through the list, keeping track of the index of each occurrence of the words. In this case, "practice" is at index 0 and "coding" is at index 3, the shortest distance between them is 3 - 0 = 3.

Approach

Our solution will use an unordered_map (or dictionary), data structure to store the words in the form of key-value pairs where the key is each word in the array and the value is a list of indexes at which it occurs.

At any point, if we wish to find the shortest distance between two words, we check their respective lists and calculate the difference between each pair of indices (one from the first word list and one from the second). We keep track of the minimum of these differences which will be our result.

Python Solution

1
2python
3class WordDistance:
4
5    def __init__(self, words):
6        self.locations = collections.defaultdict(list)
7        # Populating the locations map
8        for i, w in enumerate(words):
9            self.locations[w].append(i)
10
11    def shortest(self, word1: str, word2: str) -> int:
12        loc1, loc2 = self.locations[word1], self.locations[word2]
13        i, j, min_len = 0, 0, float('inf')
14        while i < len(loc1) and j < len(loc2):
15            min_len = min(min_len, abs(loc1[i] - loc2[j]))
16            if loc1[i] < loc2[j]:
17                i += 1
18            else:
19                j += 1
20        return min_len

Java Solution

1
2java
3class WordDistance {
4    private Map<String, List<Integer>> map;
5    public WordDistance(String[] words) {
6        map = new HashMap<String, List<Integer>>();
7        for(int i = 0; i < words.length; i++) {
8            String w = words[i];
9            if(map.containsKey(w)) {
10                map.get(w).add(i);
11            } else {
12                List<Integer> list = new ArrayList<Integer>();
13                list.add(i);
14                map.put(w, list);
15            }
16        }
17    }
18
19    public int shortest(String word1, String word2) {
20        List<Integer> list1 = map.get(word1);
21        List<Integer> list2 = map.get(word2);
22        int ret = Integer.MAX_VALUE;
23        for(int i = 0, j = 0; i < list1.size() && j < list2.size(); ) {
24            int index1 = list1.get(i), index2 = list2.get(j);
25            if(index1 < index2) {
26                ret = Math.min(ret, index2 - index1);
27                i++;
28            } else {
29                ret = Math.min(ret, index1 - index2);
30                j++;
31            }
32        }
33        return ret;
34    }
35}

C++ Solution

1
2cpp
3class WordDistance {
4public:
5    WordDistance(vector<string>& words) {
6        for (int i = 0; i < words.size(); i++)
7            wordInd[words[i]].push_back(i);
8    }
9
10    int shortest(string word1, string word2) {
11        vector<int>& indexes1 = wordInd[word1];
12        vector<int>& indexes2 = wordInd[word2];
13        int m = indexes1.size(), n = indexes2.size();
14        int i = 0, j = 0, dist = INT_MAX;
15        while (i < m && j < n) {
16            dist = min(dist, abs(indexes1[i] - indexes2[j]));
17            if (indexes1[i] < indexes2[j]) i++;
18            else j++;
19        }
20        return dist;
21    }
22private:
23    unordered_map<string, vector<int>> wordInd;
24};

JavaScript Solution

1
2javascript
3class WordDistance {
4    constructor(words) {
5        this.locations = {};
6        words.forEach((word, index) =>{
7            if(word in this.locations) {
8                this.locations[word].push(index);
9            } else {
10                this.locations[word] = [index];
11            }
12        });
13    }
14
15    shortest(word1, word2) {
16        const locations1 = this.locations[word1];
17        const locations2 = this.locations[word2];
18        let l1 = 0,
19            l2 = 0,
20            minDistance = Infinity;
21
22        while(l1 < locations1.length && l2 < locations2.length) {
23            minDistance = Math.min(minDistance, Math.abs(locations1[l1] - locations2[l2]));
24            if(locations1[l1] < locations2[l2]) {
25                l1++;
26            } else {
27                l2++;
28            }
29        }
30        return minDistance;
31    }
32}

C# Solution

1
2csharp
3public class WordDistance {
4    Dictionary<string, List<int>> locs;
5    public WordDistance(string[] words) {
6        locs = new Dictionary<string, List<int>>();
7        for (int i = 0; i < words.Length; i++) {
8            if (!locs.ContainsKey(words[i]))
9                locs.Add(words[i], new List<int>());
10            locs[words[i]].Add(i);
11        }
12    }
13
14    public int Shortest(string word1, string word2) {
15        List<int> locs1, locs2;
16        locs.TryGetValue(word1, out locs1);
17        locs.TryGetValue(word2, out locs2);
18        int i = 0, j = 0, dist = Int32.MaxValue;
19        while (i < locs1.Count && j < locs2.Count) {
20            dist = Math.Min(dist, Math.Abs(locs1[i] - locs2[j]));
21            if (locs1[i] < locs2[j]) {
22                i++;
23            } else {
24                j++;
25            }
26        }
27        return dist;
28    }
29}

Each of these solutions follows a similar approach in terms of functionality. When the class is instantiated, it consumes the given list of words and maps each word to its corresponding indices in the list. This dictionary-like object allows us to quickly retrieve all the positions a particular word is in.

The shortest method works by iterating through the indices of word1 and word2 simultaneously. At each step, it calculates the absolute difference between the current indices and updates the minDistanceif this difference is less than the currentminDistance`. The respective index pointers are moved based on the comparison of the currently pointed indices.

These solutions demonstrate the application of two critical ideas. Firstly, pre-computation provides quick look-ups during runtime. By creating a map of the locations of each word, we minimize repeated manual search. Secondly, the two-pointer technique is a neat way to traverse through the two lists of word locations simultaneously, keeping the overall time complexity linear to the total number of occurrences of the two words.

Each of the solutions contains the same basic logic implemented in different programming languages, showing how a problem-solving approach can be language agnostic while the actual coding syntax may differ. This kind of approach would be particularly useful in applications like search engines, document parsers, or any Natural Language Processing(NLP) tool, which requires the measurement of semantic closeness or similarity between words in a text document.