LeetCode 599. Minimum index sum of two lists

Title address (599. The minimum index sum of two lists )

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

Title Description

 hypothesis Andy and Doris Want to choose a restaurant for dinner , And they all have a list of their favorite restaurants , The name of each restaurant is represented by a string .

 You need to help them use the least index and find their favorite restaurants .  If there is more than one answer , Then all the answers are output regardless of the order .  You can assume that there is always an answer .

 Example  1:

 Input :
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
 Output : ["Shogun"]
 explain :  Their only favorite restaurant is “Shogun”.


 Example  2:

 Input :
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
 Output : ["Shogun"]
 explain :  Their favorite restaurant with the smallest index and is “Shogun”, It has the smallest index and 1(0+1).


 Tips :

 The length range of both lists is  [1, 1000] Inside .
 The length of the strings in the two lists will be in [1,30] Within the scope of .
 Subscript from 0 Start , Reduce the length of the list by 1.
 Neither list has duplicate elements .

Ideas

Save routing weight with hash table , Then traverse the value

Code

• Language support ：Python3

Python3 Code:

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        resDict = dict()
        resList = list()
        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))
        # Yes index Sum sort , Get the value of the lowest weight , Then 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)

Complexity analysis

Make n Is array length .

• Time complexity ：$O(n)$
• Spatial complexity ：$O(n)$