Question

1257. 最小公共区域

English Version

题目描述

给你一些区域列表 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"

 

提示：

• 2 <= regions.length <= 10^4
• region1 != region2
• 所有字符串只包含英文字母和空格，且最多只有 20 个字母。

解法

方法一

class Solution:
  def findSmallestRegion(
    self, regions: List[List[str]], region1: str, region2: str
  ) -> str:
    m = {}
    for region in regions:
      for r in region[1:]:
        m[r] = region[0]
    s = set()
    while m.get(region1):
      s.add(region1)
      region1 = m[region1]
    while m.get(region2):
      if region2 in s:
        return region2
      region2 = m[region2]
    return region1

class Solution {
  public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
    Map<String, String> m = new HashMap<>();
    for (List<String> region : regions) {
      for (int i = 1; i < region.size(); ++i) {
        m.put(region.get(i), region.get(0));
      }
    }
    Set<String> s = new HashSet<>();
    while (m.containsKey(region1)) {
      s.add(region1);
      region1 = m.get(region1);
    }
    while (m.containsKey(region2)) {
      if (s.contains(region2)) {
        return region2;
      }
      region2 = m.get(region2);
    }
    return region1;
  }
}

class Solution {
public:
  string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
    unordered_map<string, string> m;
    for (auto& region : regions)
      for (int i = 1; i < region.size(); ++i)
        m[region[i]] = region[0];
    unordered_set<string> s;
    while (m.count(region1)) {
      s.insert(region1);
      region1 = m[region1];
    }
    while (m.count(region2)) {
      if (s.count(region2)) return region2;
      region2 = m[region2];
    }
    return region1;
  }
};

func findSmallestRegion(regions [][]string, region1 string, region2 string) string {
  m := make(map[string]string)
  for _, region := range regions {
    for i := 1; i < len(region); i++ {
      m[region[i]] = region[0]
    }
  }
  s := make(map[string]bool)
  for region1 != "" {
    s[region1] = true
    region1 = m[region1]
  }
  for region2 != "" {
    if s[region2] {
      return region2
    }
    region2 = m[region2]
  }
  return region1
}