Top LinkedIn Questions — Shortest Word Distance II[LC-244]

Linkedin logo, no affiliation with linkedin.

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

For this problem you are asked to implement a data structure that is constructed with a list of words like [“practice”, “makes”, “perfect”, “coding”, “makes”] and that provides a method called shortest with this signature int shortest(string word1, string word2) , that just means that it returns an integer from two strings which represents the distance between two words in the list, word1 and word2. We can assume that both are always in the original list.

Solution

For this problem the solution is simple, but has a tiny trick. The main intuition is to just keep track of the indexes of the words in a map data structure, you can use an unordered_map or even a json object {} if you use js for this question. Once you have that map generated in the constructor, you can implement the shortest method by just subtracting the indices of the words.

But what if two words appear more than once? Well we can still use the same intuition by using the concept of chaining to solve this collition. In a few words instead of keeping track of one index per word, we keep track of a list of indices. A similar concept to Chaining in a hash table. https://en.wikipedia.org/wiki/Hash_table#Separate_chaining

Once we get out two lists of indices one for each word, we just get the smallest distance by comparing all pairs O(n²). Or we can have the lists sorted on construction and return the minimum distance in O(n).

class WordDistance {
public:
    
    unordered_map<string, vector<int>> map;
    WordDistance(vector<string>& words) {
        // unordered map with chaining to solve the name collision
        for(int i =0; i < words.size(); i++){
            map[words[i]].push_back(i);
        }
        // Sorting to reduce lookup runtime. O(nlogn) due to sorting.
        for(auto& it:map){
            sort(it.second.begin(), it.second.end());
        }
    }
    
    int shortest(string word1, string word2) {
        // Get the lists we are guaranteed to have by assumption
        const vector<int> word1Index = map[word1];
        const vector<int> word2Index = map[word2];
        
        // Compute the smallest difference in two sorted lists, assuming the lists are sorted. O(n+m)
        int result = INT_MAX;
        
        int a = 0, b = 0;
        while(a<word1Index.size() && b<word2Index.size()){
            if (abs(word1Index[a] - word2Index[b]) < result) 
                result = abs(word1Index[a] - word2Index[b]); 
            
            if(word1Index[a] < word2Index[b]){
                a++;
            }else{
                b++;
            }
        }
        
        return result;
    }
};