Leetcode 1257 @ Smallest Common Region

1257. Smallest Common Region

Medium

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.

这道题就是变相的lowest common ancestor，整个2维数组给的就是一颗树，从earth出发，延伸出north america, south america。思路是这样，可是关键，我们需要构造出一棵树，然后再做lowest common ancestor么？未免有点繁琐，尤其它给的数据结构是2维数组。

那么非常直观的思路是，我们把region1, region2从顶点到末端的路线找出来，然后再一一比对，找到最低的ancestor就可以了。

那么找路线，是bottom up or top down呢？top down，可以stack, DFS。又或者bottom up，用一个hashmap来保存每一个region的parent region，这样按图索骥，就可以把region1 to root的路线找出来了。

注意一点，push back parent node时，要从i = 1开始，因为若从0开始，那么就会有parent[region] = region，后面做while find时容易不小心陷入死循环。

想一想， 如果top down, DFS该怎么做呢？

class Solution
{
    public:
    string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) 
    {
        // lowest common ancestor
        // use parents hashmap to print out the paths
        unordered_map<string, string> parents;
        vector<string> p1, p2;
        for (int i = 0; i<regions.size(); i++)
        {
            for (int j = 1; j<regions[i].size(); j++)
            {
                parents[regions[i][j]] = regions[i][0];
            }
        }
        while(!region1.empty())
        {
            p1.push_back(region1);
            region1 = parents[region1];
        }
        while(!region2.empty())
        {
            p2.push_back(region2);
            region2 = parents[region2];
        }
        for (auto &r1 : p1)
        {
            for (auto &r2 : p2)
            {
                if (r2 == r1)
                    return r1;
            }
        }
        return NULL;
    }
};