Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1257.html
1257. Smallest Common Region
Level
Medium
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
, region2
, find out 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’s 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"
Constraints:
2 <= regions.length <= 10^4
region1 != region2
- All strings consist of English letters and spaces with at most 20 letters.
Solution
Use a map to store each region and its parent. Say region X is region Y’s parent if region X directly includes region Y. Also say region X is region Z’s ancestor if there exists a path such that X -> X1 -> X2 -> … -> Xn -> Xn+1 -> … -> Z where “->” represents a parent-child relation (that is to say, Xn is a parent of Xn+1).
Use a set to store region1
and all its ancestors. Then for region2
, find the lowest ancestor that is in the set, which is the lowest ancestor of region1
. Return the lowest ancestor.
-
class Solution { public String findSmallestRegion(List<List<String>> regions, String region1, String region2) { Map<String, String> map = new HashMap<String, String>(); for (List<String> list : regions) { int size = list.size(); String first = list.get(0); for (int i = 1; i < size; i++) map.put(list.get(i), first); } Set<String> set = new HashSet<String>(); String str1 = region1; while (str1 != null) { set.add(str1); str1 = map.get(str1); } String str2 = region2; while (!set.contains(str2)) str2 = map.get(str2); return str2; } }
-
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(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 }