## 题目描述

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.

You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.

Example 1:

``````Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
Output: ["Shogun"]
Explanation: The only restaurant they both like is "Shogun".``````

Example 2:

``````Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
Output: ["Shogun"]
Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).``````

Note:

1. The length of both lists will be in the range of [1, 1000].
2. The length of strings in both lists will be in the range of [1, 30].
3. The index is starting from 0 to the list length minus 1.
4. No duplicates in both lists.

## 解法一

### Python

``````class Solution:
def findRestaurant(self, list1, list2):
"""
:type list1: List[str]
:type list2: List[str]
:rtype: List[str]
"""
min_index_sum = sys.maxsize
result = []
list1_dict = {k: v for v, k in enumerate(list1)}
for index, item in enumerate(list2):
if index > min_index_sum:
break
if item in list1_dict:
current_index_sum = index + list1_dict[item]
if current_index_sum < min_index_sum:
min_index_sum = current_index_sum
result = []
if current_index_sum == min_index_sum:
result.append(item)
return result``````

### Java

``````public class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
int minIndexSum = Integer.MAX_VALUE;
List<String> resultList = new ArrayList<>();
Map<String, Integer> list1Map = new HashMap<>();
for (int i = 0; i < list1.length; i++) {
list1Map.put(list1[i], i);
}
for (int i = 0; i < list2.length; i++) {
if (i > minIndexSum) {
break;
}
String item = list2[i];
if (list1Map.containsKey(item)) {
int currentIndexSum = i + list1Map.get(item);
if (currentIndexSum < minIndexSum) {
minIndexSum = currentIndexSum;
resultList.clear();
}
if (currentIndexSum == minIndexSum) {
}
}
}
String[] result = new String[resultList.size()];
return resultList.toArray(result);
}
}``````

### C++

``````class Solution {
public:
vector<string> findRestaurant(vector<string> &list1, vector<string> &list2) {
int minIndexSum = INT_MAX;
vector<string> result;
unordered_map<string, int> list1Map;
for (int i = 0; i < list1.size(); i++) {
list1Map.insert(pair<string, int>(list1[i], i));
}
for (int i = 0; i < list2.size(); i++) {
if (i > minIndexSum) {
break;
}
string item = list2[i];
if (list1Map.find(item) != list1Map.end()) {
int currentIndexSum = i + list1Map[item];
if (currentIndexSum < minIndexSum) {
minIndexSum = currentIndexSum;
result.clear();
}
if (currentIndexSum == minIndexSum) {
result.push_back(item);
}
}
}
return result;
}
};``````