C++ O(m+n) solution with two maps


  • 0
    R
    class Solution {
    public:
        vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
            unordered_map<string, int> m1;
            for (int i = 0; i < list1.size(); ++i) {
                m1[list1[i]] = i;
            }
    
            int cnt = INT_MAX;
            unordered_map<int, vector<string>> m2;
            for (int i = 0; i < list2.size(); ++i) {
                if (m1.count(list2[i])) {
                    int sum = m1[list2[i]] + i;
                    if (m2.count(sum)) {
                        m2[sum].push_back(list2[i]);
                    } else {
                        m2[sum] = vector<string>{list2[i]};
                    }
                    cnt = min(cnt, sum);
                }
            }
    
            return m2[cnt];
        }
    };
    

Log in to reply
 

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