Сложность: 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 {
function findRestaurant($list1, $list2) {
$map = [];
for ($i = 0; $i < count($list1); $i++) {
for ($j = 0; $j < count($list2); $j++) {
if ($list1[$i] == $list2[$j]) {
if (!isset($map[$i + $j])) {
$map[$i + $j] = [];
}
$map[$i + $j][] = $list1[$i];
}
}
}
$minIndexSum = min(array_keys($map));
return $map[$minIndexSum];
}
}Ставь 👍 и забирай 📚 Базу знаний