题目描述

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.

解法一

思路

想要得到“最小索引和”那就免不了要遍历两个数组了。注意到只有值相等的元素才能够用来计算索引和，所以我们只需要遍历其中一个数组，而把另一个数组当作Map（key为元素值，value为索引）来查表就可以了。这样在遍历其中一个数组时，对于每个元素，只用在Map中找到相同元素，得到其在另一数组中的索引，与自身的索引相加即为索引和；遍历完成得到的最小索引和即为最终结果。

这里还有一个剪枝的步骤，遍历每个元素时，我们会维护一个当前得到的最小索引和，而如果仅当前元素的索引就已经比当前最小索引和大的话，也就没有继续遍历下去的意义了（当前元素索引与Map得到的另一数组中的索引的和一定大于最小索引和）。

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) {
                    resultList.add(item);
                }
            }
        }
        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;
    }
};