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: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Explanation: The only restaurant they both like is "Shogun".

Example 2:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["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).

Example 3:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Burger King","Tapioca Express","Shogun"]
Output: ["KFC","Burger King","Tapioca Express","Shogun"]

Example 4:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KNN","KFC","Burger King","Tapioca Express","Shogun"]
Output: ["KFC","Burger King","Tapioca Express","Shogun"]

Example 5:

Input: list1 = ["KFC"], list2 = ["KFC"]
Output: ["KFC"]

Constraints:

• 1 <= list1.length, list2.length <= 1000
• 1 <= list1[i].length, list2[i].length <= 30
• list1[i] and list2[i] consist of spaces ' ' and English letters.
• All the stings of list1 are unique.
• All the stings of list2 are unique.

# @lc code=start
using LeetCode

function find_restaurant(list1::Vector{String}, list2::Vector{String})::Vector{String}
    dic = Dict(st => (i - 1) for (i, st) in enumerate(list1))
    cost, res = typemax(1), String[]
    for (i, s) in enumerate(list2)
        !haskey(dic, s) && continue
        newcost = i - 1 + dic[s]
        if newcost < cost
            cost, res = newcost, [s]
        elseif newcost == cost
            push!(res, s)
        end
    end
    return res
end

# @lc code=end

find_restaurant (generic function with 1 method)

This page was generated using DemoCards.jl and Literate.jl.