-
Notifications
You must be signed in to change notification settings - Fork 0
/
MinimumIndexSum.py
50 lines (40 loc) · 1.93 KB
/
MinimumIndexSum.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
# 599. Minimum Index Sum of Two Lists
# 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:
# The length of both lists will be in the range of [1, 1000].
# The length of strings in both lists will be in the range of [1, 30].
# The index is starting from 0 to the list length minus 1.
# No duplicates in both lists.
class Solution:
def findRestaurant(self, list1, list2):
# Construct dictionary of first list with items as key and index as values
items = {}
for i, item in enumerate(list1):
items[item] = i
# Construct a dictionary with matches and their distances
results = {}
for i, item in enumerate(list2):
if item in items:
results[item] = items[item] + i
# Construct a list with only the smaller ones.
result = []
minDistance = min(results.values())
for match, distance in results.items():
if distance <= minDistance:
result.append(match)
return result
print(Solution().findRestaurant(["Shogun", "Tapioca Express", "Burger King", "KFC"],
["KFC", "Shogun", "Burger King"]))