My simple c++ solution


  • 0
    K
    class WordDistance {
      unordered_map<string, vector<int>>map;
    public:
    WordDistance(vector<string>& words) {
        
        for(int i=0; i < words.size(); i++)map[words[i]].push_back(i);
    }
    
    int shortest(string word1, string word2) {
        vector<int>w1=map[word1], w2=map[word2];
        int dist=INT_MAX;
        
        for(auto & index1 : w1)
            for(auto &index2 : w2){
                if(abs(index1- index2) < dist)dist=abs(index1-index2);
            }
        return dist;
    }
    

    };


  • 0

    The loop "for(auto & index1 : w1)
    for(auto &index2 : w2){"
    has O(w1.size()*w2.size()) time cost. This can be improved to O(w1.size() + w2.size()) cost if you just keep increment smaller index between your index1 and index2 each time. There is no need to go back to compare the very first index very time.


  • 0
    F

    This is the perfect solution for an interview. It's clean, easy to do in 10 minutes or so, and decently performant. I ended up with something nearly identical. An optimization is to return early if the outer loop's index is less than the inner loop's index. Every further iteration in the inner loop is just going to result in a larger distance in that case.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.