9-line O(n) C++ Solution


  • 21
    class WordDistance {
    public:
        WordDistance(vector<string>& words) {
            for(int i=0;i<words.size();i++)
                wordMap[words[i]].push_back(i);
        }
        int shortest(string word1, string word2) {
            int  i=0, j=0, dist = INT_MAX;
            while(i < wordMap[word1].size() && j <wordMap[word2].size()) { 
                dist = min(dist, abs(wordMap[word1][i] - wordMap[word2][j]));
                wordMap[word1][i]<wordMap[word2][j]?i++:j++;
            }
            return dist;
        }
    private:
        unordered_map<string, vector<int>> wordMap;
    };

  • 0
    A

    Nice code. If you add the following "if" line before the while loop, your code will be faster.

    int  i = 0, j = 0, dist = INT_MAX;
    
    if ( wordMap[word1].size() == 1 && wordMap[word2].size() == 1 ) {
        return abs(wordMap[word1][0] - wordMap[word2][0]);
    }
    
    while ( i < wordMap[word1].size() && j < wordMap[word2].size() ) {
    ...
    

  • 0
    G

    If you use references of the vectors instead of calling wordMap[], the performance seems to improve.


  • 0

    Since this problem states that the "shortest" call will be made repeated, is it better to define a hash map with key type pair<string, string> (make string1 < string2 for uniqueness) in the class? And record its value whenever a new pair (word1, word2) is called, so we do not compute again for the same input pair.


Log in to reply
 

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