1257 - Smallest Common Region.

对比lca

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 and region2, return 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 is 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"

Example 2:

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

Constraints:

• 2 <= regions.length <= 104

• 2 <= regions[i].length <= 20

• 1 <= regions[i][j].length, region1.length, region2.length <= 20

• region1 != region2

• regions[i][j], region1, and region2 consist of English letters.

• The input is generated such that there exists a region which contains all the other regions, either directly or indirectly.

LCA难在往下走，所以需要回溯。这里MAP是son->father, 直接拿到一个子的所有父亲，和另一个子的父亲们比较即可。

注意dict.get(key)和dict[key]区别，前者返回NONE

class Solution:
    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:
        parents = {child : region[0] for region in regions for child in region[1:]} #son:father

        ancester = set()
        while region1:
            ancester.add(region1)
            region1 = parents.get(region1)
            
        
        while region2 not in ancester:
            region2 = parents[region2]
        
        return region2