Python, 5 lines, O(n) time, O(n) space


  • 1
    M
    class Solution(object):
        def findRestaurant(self, list1, list2):
            """
            :type list1: List[str]
            :type list2: List[str]
            :rtype: List[str]
            """
            dict1 = {rest : i for i, rest in enumerate(list1)}
            dict2 = {rest : i for i, rest in enumerate(list2)}
            dictSum = {rest : dict1[rest]+dict2[rest] for rest in dict1 if rest in dict2}
            minSum = min(dictSum.values())
            return [key for key in dictSum if dictSum[key] == minSum]
    

    Or a little bit faster solution:

    class Solution(object):
        def findRestaurant(self, list1, list2):
            """
            :type list1: List[str]
            :type list2: List[str]
            :rtype: List[str]
            """
            dict1 = {rest : i for i, rest in enumerate(list1)}
            dict2 = {rest : i for i, rest in enumerate(list2)}
            dictSum = {rest : dict1[rest]+dict2.get(rest, 2017) for rest in dict1}
            minSum = min(dictSum.values())
            return [key for key in dictSum if dictSum[key] == minSum]
    

    The fourth line in both solutions could be in the last one (return [key for key in dictSum if dictSum[key] == min(dictSum.values())), but that makes it slower. Is that because it calculates the min again every iteration?


  • 0
    P

    @Matti :I didn't get why dict2.get(rest, 2017) in the second option 3rd line,could you please explain?


  • 0
    M

    @pygirl5 dict2.get(rest, 2017) returns the index of current restaurant from list2. If the restaurant is not in this list, then it returns 2017 instead, which is just a nice number I picked, it only needs to be greater than 1998. We are allowed to assume it always has a solution and that the lists length is in the range of [1, 1000], hence in the worst case the correct answer's sum of indexes will be 999+999=1998.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.