Description:
https://leetcode.com/problems/minimum-index-sum-of-two-lists/#/description
My first code: ( Time is not good)
class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
int sum = 2000;
vector<string> name;
for (int i = 0; i < list1.size();i++)
{
for (int j = 0; j < list2.size();j++)
{
if (list1[i] == list2[j] && i + j < sum)
{
sum = i+j;
name.clear();
name.push_back(list1[i]);
}
else if (list1[i] == list2[j] && i + j == sum)
{
sum = i+j;
name.push_back(list1[i]);
}
}
}
return name;
}
};
/*********************************************************************************************/
The algorithm can be optimized by using unordered map.
My Second code:
class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
unordered_map<string, int> table;
table.reserve(list1.size());
for (int i = 0; i < list1.size(); ++i) {
table[list1[i]] = i;
}
int sum = list1.size() + list2.size();
for (int j = 0; j < list2.size(); ++j) {
auto it = table.find(list2[j]);
if (it != table.end() && it->second + j < sum) {
sum = it->second + j;
}
}
vector<string> results;
for (int j = 0; j < list2.size(); ++j) {
auto it = table.find(list2[j]);
if (it != table.end() && it->second + j == sum) {
results.emplace_back(list2[j]);
}
}
return results;
}
};