Simple C++ solution with map


  • 0
    T

    Simple C++ solution with map.

    Space complexity is O(min(M,N)) where M and N are the lengths of the lists.

    Here is the code:

    class Solution {
    public:
        vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
            int len1 = list1.size(),
                len2 = list2.size();
            if (len1 > len2) {
                swap(list1, list2);
                swap(len1, len2);
            }
    
            map<string, int> indexInL1;
            for (int i = 0; i < len1; ++i) {
                indexInL1[list1[i]] = i;
            }
    
            int best = INT_MAX;
            for (int i = 0; i < len2; ++i) {
                string& word = list2[i];
                if (!indexInL1.count(word)) continue;
                int value = indexInL1[word] + i;
                if (value < best) best = value;
            }
    
            vector<string> res;
            for (int i = 0; i < len2; ++i) {
                string& word = list2[i];
                if (indexInL1.count(word) && indexInL1[word] + i == best)
                    res.push_back(word);
            }
    
            return res;
        }
    };
    

Log in to reply
 

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