Subject address (599. Minimum index sum for two lists)

Leetcode-cn.com/problems/mi…

Topic describes

Let's say Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants, with the name of each restaurant represented by a string. You need to help them find their favorite restaurants with minimal indexing. If there is more than one answer, all answers are printed regardless of order. You can assume there is always an answer. Example 1: Enter: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", ["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: Their favorite restaurant with the smallest index sum is "Shogun", which has the smallest index and 1(0+1). Tip: Both lists are within the length range of [1, 1000]. The strings in both lists will be in the range of [1,30]. The subscript starts at 0 and goes to the length of the list minus 1. There are no duplicate elements in either list.Copy the code

Train of thought

Save the route weights in a hash table and iterate over the values

code

  • Language support: Python3

Python3 Code:


class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) - >List[str] :
        resDict = dict()
        resList = list(a)for index,val in enumerate(list1):
            resDict[val] = index
        for index,val in enumerate(list2):
            if val in resDict:
                resList.append((index+resDict[val],val))
        # sort the sum of index, get the lowest weight value, and extract the same value
        resList.sort(key=lambda x:x[0])
        res = []
        resIndex = resList[0] [0]
        for indexCount,val in resList:
            if indexCount == resIndex:
                res.append(val)
        return res

if __name__ == '__main__':
    list1 = ["Shogun"."Tapioca Express"."Burger King"."KFC"]
    list2 = ["KFC"."Shogun"."Burger King"]
    ret = Solution().findRestaurant(list1,list2)
    print(ret)

Copy the code

Complexity analysis

Let n be the length of the array.

  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)