preface

Record the leetcode problem for the day

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 the answer is always there.

Example 1

Input: List1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"], List2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"] The only restaurant they love together is Shogun.Copy the code

Example 2

Input :list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"], list2 = ["KFC", "Shogun", "Burger King"] ["Shogun"] Explanation: Their favorite restaurant with the smallest index sum is "Shogun", which has the smallest index and 1(0+1).Copy the code

prompt

  • 1 <= list1.length, list2.length <= 1000
  • 1 <= list1[i].length, list2[i].length <= 30 
  • List1 [I] and list2[I] consist of Spaces and letters.
  • All strings for List1 are unique.
  • All strings in list2 are unique.

Train of thought

Similar to duplicate lookup, you can create a table to store the first person’s restaurant list and index. Iterate over the second restaurant list to see if it exists in the current table. Here, a variable can be created to store the current minimum index of both restaurants. If both restaurants have subindexes less than the minimum index, then this restaurant is considered to be the minimum index and the favorite restaurant. If it is equal to the minimum index, then there can be multiple restaurants that meet the conditions

code

/ * * *@param {string[]} list1
 * @param {string[]} list2
 * @return {string[]}* /
var findRestaurant = function (list1, list2) {
    const hash = new Map(a)let result = []
    // Stores the first traversed data into the hash using the subscript
    list1.forEach((item, index) = > {
        hash.set(item, index)
    })
    let minIndex = Number.MAX_VALUE // Store the current minimum index
    list2.forEach((item, index) = > {
        if (hash.has(item)) {
            if (index + hash.get(item) < minIndex) {
                // Determine whether their minimum index is smaller than the current record
                result.length = 0 // Clear the previous data
                minIndex = index + hash.get(item) // Recalculate current minimum index
                result.push(item) // Store public restaurants
            } else if (index + hash.get(item) == minIndex) {
                result.push(item) // Multiple common favorites are represented here}}})return result
};
Copy the code

The last

Make a little progress every day