599. Minimum Index Sum of Two Lists

leetcode easy

#array#csharp#easy#hash-table#leetcode#math#search#string

Task

Даны два массива строк list1 и list2, необходимо найти общие строки с наименьшей суммой индексов.

Общая строка - это строка, которая появляется и в list1, и в list2.

Общая строка с наименьшей суммой индексов - это общая строка, такая, что если она появилась в list1[i] и list2[j], то i + j должно быть минимальным значением среди всех других общих строк.

Верните все общие строки с наименьшей суммой индексов. Верните ответ в любом порядке.

Пример:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]

Output: ["Shogun"]

Explanation: The only common string is "Shogun".

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public string[] FindRestaurant(string[] list1, string[] list2) {
        var map = new Dictionary<int, List<string>>();
        for (int i = 0; i < list1.Length; i++) {
            for (int j = 0; j < list2.Length; j++) {
                if (list1[i] == list2[j]) {
                    if (!map.ContainsKey(i + j)) {
                        map[i + j] = new List<string>();
                    }
                    map[i + j].Add(list1[i]);
                }
            }
        }
        int minIndexSum = int.MaxValue;
        foreach (var key in map.Keys) {
            minIndexSum = Math.Min(minIndexSum, key);
        }
        return map[minIndexSum].ToArray();
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<string> FindRestaurant(vector<string> list1, vector<string> list2) {
        var map = new unordered_map<int, List<string>>();
        for (int i = 0; i < list1.size(); i++) {
            for (int j = 0; j < list2.size(); j++) {
                if (list1[i] == list2[j]) {
                    if (!map.count(i + j)) {
                        map[i + j] = new List<string>();
                    }
                    map[i + j].push_back(list1[i]);
                }
            }
        }
        int minIndexSum = int.MaxValue;
        foreach (var key in map.Keys) {
            minIndexSum = min(minIndexSum, key);
        }
        return map[minIndexSum].ToArray();
    }
}

Java solution

matched/original

import java.util.*;

public class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        HashMap<Integer, List<String>> map = new HashMap<>();
        for (int i = 0; i < list1.length; i++) {
            for (int j = 0; j < list2.length; j++) {
                if (list1[i].equals(list2[j])) {
                    if (!map.containsKey(i + j)) {
                        map.put(i + j, new ArrayList<>());
                    }
                    map.get(i + j).add(list1[i]);
                }
            }
        }
        int minIndexSum = Integer.MAX_VALUE;
        for (int key : map.keySet()) {
            minIndexSum = Math.min(minIndexSum, key);
        }
        return map.get(minIndexSum).toArray(new String[0]);
    }
}

JavaScript solution

matched/original

var findRestaurant = function(list1, list2) {
    let map = new Map();
    for (let i = 0; i < list1.length; i++) {
        for (let j = 0; j < list2.length; j++) {
            if (list1[i] === list2[j]) {
                if (!map.has(i + j)) {
                    map.set(i + j, []);
                }
                map.get(i + j).push(list1[i]);
            }
        }
    }
    let minIndexSum = Math.min(...map.keys());
    return map.get(minIndexSum);
};

Python solution

matched/original

class Solution:
    def findRestaurant(self, list1, list2):
        map = {}
        for i in range(len(list1)):
            for j in range(len(list2)):
                if list1[i] == list2[j]:
                    if i + j not in map:
                        map[i + j] = []
                    map[i + j].append(list1[i])
        min_index_sum = min(map.keys())
        return map[min_index_sum]

Go solution

matched/original

func findRestaurant(list1 []string, list2 []string) []string {
    map := make(map[int][]string)
    for i := 0; i < len(list1); i++ {
        for j := 0; j < len(list2); j++ {
            if list1[i] == list2[j] {
                if _, ok := map[i+j]; !ok {
                    map[i+j] = []string{}
                }
                map[i+j] = append(map[i+j], list1[i])
            }
        }
    }
    minIndexSum := int(^uint(0) >> 1)
    for key := range map {
        if key < minIndexSum {
            minIndexSum = key
        }
    }
    return map[minIndexSum]
}

Explanation

Algorithm

Для каждой строки из list1, сравниваем её с каждой строкой из list2, обходя весь список list2. Используем хэш-таблицу map, которая содержит элементы в виде (сумма: список строк). Здесь сумма относится к сумме индексов совпадающих элементов, а список строк соответствует списку совпадающих строк, чья сумма индексов равна этой сумме.

Во время сравнений, когда находится совпадение строки на i-м индексе из list1 и j-м индексе из list2, создаём запись в map, соответствующую сумме i + j, если такая запись ещё не существует. Если запись с этой суммой уже существует, добавляем текущую строку в список строк, соответствующих сумме i + j.

В конце обходим ключи в map и находим список строк, соответствующих ключу с минимальной суммой.

😎