Description
You are given some lists of regions
where the first region of each list includes all other regions in that list.
Naturally, if a region x
contains another region y
then x
is bigger than y
. Also, by definition, a region x
contains itself.
Given two regions: region1
and region2
, return the smallest region that contains both of them.
If you are given regions r1
, r2
, and r3
such that r1
includes r3
, it is guaranteed there is no r2
such that r2
includes r3
.
It is guaranteed the smallest region exists.
Example 1:
Input:
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"
Output: "North America"
Example 2:
Input: 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"
Output: "Earth"
Constraints:
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
, and region2
consist of English letters.
Solutions
Solution 1
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
}
|