1257. Smallest Common Region
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| class Solution {
public:
string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
unordered_map<string, int> idmp;
unordered_map<string, string> parmp;
unordered_map<string, vector<string>> adj;
unordered_map<string, int> level;
int id = 1;
for(auto& rs : regions) {
for(int i = 1; i < rs.size(); i++) {
auto par = rs[0], child = rs[i];
if(!idmp.count(par)) idmp[par] = id++;
if(!idmp.count(child)) idmp[child] = id++;
parmp[child] = par;
adj[par].push_back(child);
}
}
string root = "";
for(auto [r, id] : idmp) {
if(parmp.count(r)) continue;
root = r;
}
queue<string> q;
q.push(root);
level[root] = 0;
int lvl = 1;
while(!q.empty()) {
int sz = q.size();
while(sz--) {
auto u = q.front(); q.pop();
for(auto& v : adj[u]) {
q.push(v);
level[v] = lvl;
}
}
lvl++;
}
while(region1 != region2) {
if(level[region1] > level[region2]) region1 = parmp[region1];
else if(level[region1] < level[region2]) region2 = parmp[region2];
else {
region1 = parmp[region1];
region2 = parmp[region2];
}
}
return region1;
}
};
|
