Simulate merging of two sorted arrays: C++ solution, O(N*log N) time, O(N) space


  • 0
    X
    int shortestDistance(vector<string>& words, string word1, string word2) {
        unordered_map<string, set<size_t>> positions;
        for(size_t i = 0; i < words.size(); ++i) positions[words[i]].insert(i);
    
        auto pos1 = positions[word1];
        auto pos2 = positions[word2];
        
        auto it1 = pos1.begin();
        auto it2 = pos2.begin();
        
        if(*it2 < *it1)
        {
            swap(it1, it2);
            swap(pos1, pos2);
        }
        
        auto distance = *it2 - *it1;
        auto last1 = *it1;
        for(;;)
        {
            while(it1 != pos1.end() && *it1 <= *it2)
            {
                last1 = *it1;
                ++it1;
            }
            distance = min(*it2 - last1, distance);
            
            if(it1 == pos1.end()) return distance;
            
            swap(it1, it2);
            swap(pos1, pos2);
        }
        return distance;
    }

Log in to reply
 

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