C++ solution with hash and reverse index


  • 0
    S
    class Solution {
    public:
        vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
            unordered_map<string, int> hash1;
            for (int i = 0; i < list1.size(); i++) {
                hash1[list1[i]] = i;
            }
            unordered_map<int, vector<string> > ans;
            int min = 99999999;
            for (int j = 0; j < list2.size(); j++) {
                auto got = hash1.find(list2[j]);
                if (got != hash1.end()) {
                    int common = got->second + j;
                    if (common <= min) {
                        min = common;
                        ans[min].push_back(list2[j]);
                    }
                }
            }
            return ans[min];
        }
    };

  • 4
    J

    should not use common <= min, and part of code is unnecessary.

    class Solution {
      public:
        vector<string> findRestaurant(vector<string> &list1,
                                      vector<string> &list2) {
            unordered_map<string, int> hash1;
            for (size_t i = 0; i < list1.size(); ++i) {
                hash1[list1[i]] = i;
            }
    
            vector<string> ans;
            int min_sum = INT_MAX;
    
            for (size_t i = 0; i < list2.size(); i++) {
                auto got = hash1.find(list2[i]);
                if (got != hash1.cend()) {
                    int index_sum = got->second + i;
                    
                    if (index_sum < min_sum) {
                        min_sum = index_sum;
                        ans.clear();
                        ans.push_back(list2[i]);
                    } else if (index_sum == min_sum) {
                        ans.push_back(list2[i]);
                    }
                }
            }
    
            return ans;
        }
    };
    

Log in to reply
 

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