1257. Smallest Common Region - cocoder39/coco39_LC GitHub Wiki

1257. Smallest Common Region

pretty much lowest common ancestor

class Solution:
    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:
        parent = {}
        for regionList in regions:
            for i in range(1, len(regionList)):
                parent[regionList[i]] = regionList[0]
                
        path1 = self.getParents(region1, parent)[::-1]
        path2 = self.getParents(region2, parent)[::-1]
        
        res = None
        for regionA, regionB in zip(path1, path2):
            if regionA == regionB:
                res = regionA
            else:
                break
        return res
        
    
    def getParents(self, startRegion: str, parents: dict) -> List[str]:
        path = [startRegion]
        while startRegion in parents:
            startRegion = parents[startRegion]
            path.append(startRegion)
        return path