Leetcode 1257：最小公共区域_综合

给你一些区域列表 regions ，每个列表的第一个区域都包含这个列表内所有其他区域。

很自然地，如果区域 X 包含区域 Y ，那么区域 X 比区域 Y 大。

给定两个区域 region1 和 region2 ，找到同时包含这两个区域的最小区域。

如果区域列表中 r1 包含 r2 和 r3 ，那么数据保证 r2 不会包含 r3 。

数据同样保证最小公共区域一定存在。

示例 1：

输入：
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"
输出："North America"

相似例题
Leetcode 236：二叉树的最近公共祖先


def findSmallestRegion(regions, region1, region2) :parent = {
    r: region[0] for region in regions for r in region[1:]}parent[regions[0][0]]=regions[0][0]if parent[region1]==region2:return region2if parent[region2]==region1:return region1if parent[region1]==parent[region2]:return parent[region1]return findSmallestRegion(regions,parent[region1],parent[region2])if __name__ == "__main__":# print("please input 二维数组长度：")# m=int(input())# regions=[[] for _ in range (m)]# for i in range(m):# line=input().split(',')# for j in range(len(line)):# regions[i].append(line[j])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 = "Boston"res=findSmallestRegion(regions,region1, region2)

非递规实现

def findSmallestRegion(regions, region1, region2) :parent = {
    r: region[0] for region in regions for r in region[1:]}parent[regions[0][0]]=regions[0][0]while (region1!=region2):if parent[region1]==region2:region1=region2elif parent[region2]==region1:region2=region1elif parent[region1]==parent[region2]:region1=parent[region1]region2=region1else:region1=parent[region1]region2=parent[region2]return region1