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


  • 0
    X

    I approached the "Shortest Word Distance I" problem already using the necessary auxiliary words positions map, so it wasn't a big deal to separate the logic between the constructor and main algorithm. The only thing I realized in addition to that is that we don't have to use set to sort the positions, since they are already inserted in a sorted order, so can just use vector.

      class WordDistance {
            unordered_map<string, vector<size_t>> positions;
        public:
            WordDistance(vector<string>& words) {
                for(size_t i = 0; i < words.size(); ++i) positions[words[i]].push_back(i);
            }
        
            int shortest(string word1, string word2) {
                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.