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`, `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"],
["United States","New York","Boston"],
["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.

1257. Smallest Common Region
``````struct Solution;
use std::collections::HashMap;
use std::collections::HashSet;

impl Solution {
fn find_smallest_region(regions: Vec<Vec<String>>, region1: String, region2: String) -> String {
let mut parent: HashMap<&String, &String> = HashMap::new();
for list in &regions {
let n = list.len();
for i in 1..n {
parent.insert(&list[i], &list[0]);
}
}
let mut path: HashSet<&String> = HashSet::new();
let mut p1 = &region1;
let mut p2 = &region2;
path.insert(p1);
while let Some(next) = parent.get(p1) {
p1 = next;
path.insert(p1);
}
if path.contains(p2) {
return p2.to_string();
}
while let Some(next) = parent.get(p2) {
p2 = next;
if path.contains(p2) {
return p2.to_string();
}
}
"".to_string()
}
}

#[test]
fn test() {
let regions = vec_vec_string![
["Earth", "North America", "South America"],
["United States", "New York", "Boston"],
["South America", "Brazil"]
];
let region1 = "Quebec".to_string();
let region2 = "New York".to_string();
let res = "North America".to_string();
assert_eq!(
Solution::find_smallest_region(regions, region1, region2),
res
);
let regions = vec_vec_string![
["Earth", "North America", "South America"],