LeetCode 1257 - Smallest Common Region

https://www.cnblogs.com/seyjs/p/11878841.html

You are given some lists of regions where the first region of each list includes all other regions in that list.

Naturally, if a region X contains another region Y then X is bigger than Y. Also by definition a region X contains itself.

Given two regions region1, region2, find out the smallest region that contains both of them.

If you are given regions r1, r2 and r3 such that r1 includes r3, it is guaranteed there is no r2 such that r2 includes r3.

It's guaranteed the smallest region exists.

Example 1:

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"

Constraints:

• 2 <= regions.length <= 10^4
• region1 != region2
• All strings consist of English letters and spaces with at most 20 letters.

https://www.acwing.com/file_system/file/content/whole/index/content/150816/

(暴力枚举) $O(n)$

1. 根据题目描述，区域构成的数据结构就是一棵树，每个列表给出的是边关系。（如果不是树则不能保证最近公共祖先一定存在）。
2. 每个区域记录下自己的父亲区域，然后暴力求出 region1 的祖先区域列表，然后在 region2 求的过程中匹配最近的 region1 的区域列表。

时间复杂度

• 遍历一次区域列表，然后遍历两个区域的祖先，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间记录每个区域的父亲，以及 region1 的祖先区域列表。

    string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
        unordered_map<string, string> fa;

        for (const auto &v : regions)
            for (int i = 1; i < v.size(); i++)
                fa[v[i]] = v[0];

        unordered_set<string> anc;

        while (fa.find(region1) != fa.end()) {
            anc.insert(region1);
            region1 = fa[region1];
        }

        anc.insert(region1);

        while (fa.find(region2) != fa.end()) {
            if (anc.find(region2) != anc.end())
                return region2;
            region2 = fa[region2];
        }

        return region2;
    }

首先递归找出region1所属的regions链，并保持结果；然后再递归查找region2所属的regions链，找到第一个region在region1所属的regions链即可。

    def findSmallestRegion(self, regions, region1, region2):
        """
        :type regions: List[List[str]]
        :type region1: str
        :type region2: str
        :rtype: str
        """
        dic = {}
        for region in regions:
            parent = region[0]
            for i in range(1,len(region)):
                dic[region[i]] = parent

        dic_region1 = {}
        while region1 in dic:
            dic_region1[region1] = 1
            region1 = dic[region1]

        while region2 in dic:
            if region2 in dic_region1:
                return region2
            region2 = dic[region2]
        return regions[0][0]