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)