> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/airbnb2025/1257-smallest-common-region..md).

# 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:**

<pre><code><strong>Input:
</strong>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"
<strong>Output: "North America"
</strong></code></pre>

**Example 2:**

<pre><code><strong>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"
</strong><strong>Output: "Earth"
</strong></code></pre>

&#x20;

**Constraints:**

* `2 <= regions.length <= 10`<sup>`4`</sup>
* `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
```