# 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` 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.


def region_chain(larger_region_of, sub_region):
    address = []
    while sub_region != None:
        address.append(sub_region)
        sub_region = larger_region_of.get(sub_region, None)
    return address  # A list of regions, from small to large.

class Solution:
    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:
        larger_region_of = {}
        for li in regions:
            larger_region  = li[0]
            for smaller_region in li[1:]:
                larger_region_of[smaller_region] = larger_region
        
        address1 = region_chain(larger_region_of, region1)
        address2 = region_chain(larger_region_of, region2)
            
        address1 = set(address1)
        
        for region in address2:
            if region in address1:
                return region
            
        return -1