Сложность: easy
Даны два массива строк 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".
👨💻 Алгоритм:
1⃣Для каждой строки из list1, сравниваем её с каждой строкой из list2, обходя весь список list2. Используем хэш-таблицу map, которая содержит элементы в виде (сумма: список строк). Здесь сумма относится к сумме индексов совпадающих элементов, а список строк соответствует списку совпадающих строк, чья сумма индексов равна этой сумме.
2⃣Во время сравнений, когда находится совпадение строки на i-м индексе из list1 и j-м индексе из list2, создаём запись в map, соответствующую сумме i + j, если такая запись ещё не существует. Если запись с этой суммой уже существует, добавляем текущую строку в список строк, соответствующих сумме i + j.
3⃣В конце обходим ключи в map и находим список строк, соответствующих ключу с минимальной суммой.
😎 Решение:
class Solution {
func findRestaurant(_ list1: [String], _ list2: [String]) -> [String] {
var map = [Int: [String]]()
for i in 0..<list1.count {
for j in 0..<list2.count {
if list1[i] == list2[j] {
if map[i + j] == nil {
map[i + j] = [String]()
}
map[i + j]!.append(list1[i])
}
}
}
let minIndexSum = map.keys.min()!
return map[minIndexSum]!
}
}Ставь 👍 и забирай 📚 Базу знаний