-
Notifications
You must be signed in to change notification settings - Fork 17
/
smallest-common-region.py
44 lines (31 loc) · 1.18 KB
/
smallest-common-region.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from typing import List
from functools import lru_cache
class Region:
def __init__(self, name):
self.name = name
self.children = set()
self.parent = None
class Solution:
def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:
region_map = {}
for region in regions:
node = region_map.get(region[0], Region(region[0]))
region_map[node.name] = node
for sub_region in region[1:]:
sub_node = region_map.get(sub_region, Region(sub_region))
region_map[sub_node.name] = sub_node
node.children.add(sub_node)
sub_node.parent = node
@lru_cache
def find_lca(name, source, target):
if name == target:
return True
node = region_map[name]
for sub_node in node.children:
if find_lca(sub_node.name, source, target):
return True
return False
cur_node = region_map[region1]
while not find_lca(cur_node.name, region1, region2):
cur_node = cur_node.parent
return cur_node.name