Daily LeetCode 599. Minimum Index Sum of Two Lists

https://leetcode.com/problems/minimum-index-sum-of-two-lists/

Easy

问题描述：

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.

题目分析：

这一题其实难度不大，但我一开始看错了题，我以为只要输出一个相对来说两个人都喜欢的餐馆即可。后来各种WA后，才发现，只要index之和相等的餐厅，都需要输出。

这一题需要设置两个字典，分别保存Andy和Doris感兴趣的餐厅restaurant以及对应的index，字典格式为：{restaurant: index}。接着，我们遍历list2，找到相同元素时，将自身index和对应元素在另一个字典中的index相加，寻找最小的index之和，并将最小index和的餐厅添加到res中。

代码：

class Solution(object):
    def findRestaurant(self, list1, list2):
        """
        :type list1: List[str]
        :type list2: List[str]
        :rtype: List[str]
        """
        min_interest_sum = 999999
        Doris_dict = {}
        res = []
        Andy_dict = {restaurant: index for index, restaurant in enumerate(list1)}

        for index, restaurant in enumerate(list2):
            if restaurant in Andy_dict:
                current_interest_sum = index + Andy_dict[restaurant]
                if current_interest_sum < min_interest_sum:
                    min_interest_sum = current_interest_sum
                    res = []
                if current_interest_sum == min_interest_sum:
                    res.append(restaurant)

        return res