跳转至

1257. 最小公共区域 🔒

题目描述

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

很自然地，如果区域 x 包含区域 y ，那么区域 x  比区域 y 大。同时根据定义，区域 x 包含自身。

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

如果给定区域 r1，r2 和 r3，使得 r1 包含 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 = [["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"
输出："Earth"

 

提示：

  • 2 <= regions.length <= 104
  • 2 <= regions[i].length <= 20
  • 1 <= regions[i][j].length, region1.length, region2.length <= 20
  • region1 != region2
  • regions[i][j]，region1 和 region2 由英语字母组成。
  • 输入保证存在一个区域直接或间接包含所有其他区域。

解法

方法一

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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
}

评论