Задача: 1257. Smallest Common Region
Сложность: medium

Вам даны списки регионов, в которых первый регион каждого списка включает все остальные регионы этого списка. Естественно, если регион x содержит другой регион y, то x больше y. Также, по определению, регион x содержит сам себя. Даны два региона: region1 и region2, верните наименьший регион, который содержит их оба. Если вам даны регионы r1, r2 и r3 такие, что r1 включает r3, то гарантированно не существует r2 такого, что r2 включает r3. Гарантированно существует наименьший регион.

Пример:

Input:
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
Output: "North America"

👨‍💻 Алгоритм:

1⃣Построим дерево регионов, где каждый регион указывает на своего родителя.

2⃣Используя родительскую информацию, найдем путь от каждого региона до корня.

3⃣Найдем последний общий регион в путях двух заданных регионов.

😎 Решение:

class Solution {
    function findSmallestRegion($regions, $region1, $region2) {
        $parent = [];

        foreach ($regions as $regionList) {
            for ($i = 1; $i < count($regionList); $i++) {
                $parent[$regionList[$i]] = $regionList[0];
            }
        }

        $ancestors1 = [];
        while ($region1 !== null) {
            $ancestors1[$region1] = true;
            $region1 = isset($parent[$region1]) ? $parent[$region1] : null;
        }

        while (!isset($ancestors1[$region2])) {
            $region2 = isset($parent[$region2]) ? $parent[$region2] : null;
        }

        return $region2;
    }
}

Ставь 👍 и забирай 📚 Базу знаний