1257. Smallest Common Region

leetcode medium

#csharp#hash-table#leetcode#medium#search#string#tree

Task

Вам даны списки регионов, в которых первый регион каждого списка включает все остальные регионы этого списка. Естественно, если регион x содержит другой регион y, то x больше y. Также, по определению, регион x содержит сам себя. Даны два региона: region1 и region2, верните наименьший регион, который содержит их оба. Если вам даны регионы r1, r2 и r3 такие, что r1 включает r3, то гарантированно не существует r2 такого, что r2 включает r3. Гарантированно существует наименьший регион.

Пример:

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"

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public string FindSmallestRegion(IList<IList<string>> regions, string region1, string region2) {
        var parent = new Dictionary<string, string>();
        foreach (var regionList in regions) {
            for (int i = 1; i < regionList.Count; i++) {
                parent[regionList[i]] = regionList[0];
            }
        }
        var ancestors1 = new HashSet<string>();
        while (region1 != null) {
            ancestors1.Add(region1);
            region1 = parent.ContainsKey(region1) ? parent[region1] : null;
        }
        while (!ancestors1.Contains(region2)) {
            region2 = parent[region2];
        }
        return region2;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string FindSmallestRegion(IList<vector<string>> regions, string region1, string region2) {
        var parent = new unordered_map<string, string>();
        foreach (var regionList in regions) {
            for (int i = 1; i < regionList.size(); i++) {
                parent[regionList[i]] = regionList[0];
            }
        }
        var ancestors1 = new HashSet<string>();
        while (region1 != null) {
            ancestors1.push_back(region1);
            region1 = parent.count(region1) ? parent[region1] : null;
        }
        while (!ancestors1.Contains(region2)) {
            region2 = parent[region2];
        }
        return region2;
    }
}

Java solution

matched/original

import java.util.*;

public class Solution {
    public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
        Map<String, String> parent = new HashMap<>();

        for (List<String> regionList : regions) {
            for (int i = 1; i < regionList.size(); i++) {
                parent.put(regionList.get(i), regionList.get(0));
            }
        }

        Set<String> ancestors1 = new HashSet<>();
        while (region1 != null) {
            ancestors1.add(region1);
            region1 = parent.get(region1);
        }

        while (!ancestors1.contains(region2)) {
            region2 = parent.get(region2);
        }

        return region2;
    }
}

JavaScript solution

matched/original

var findSmallestRegion = function(regions, region1, region2) {
    const parent = new Map();

    regions.forEach(regionList => {
        for (let i = 1; i < regionList.length; i++) {
            parent.set(regionList[i], regionList[0]);
        }
    });

    const ancestors1 = new Set();
    while (region1) {
        ancestors1.add(region1);
        region1 = parent.get(region1);
    }

    while (!ancestors1.has(region2)) {
        region2 = parent.get(region2);
    }

    return region2;
};

Go solution

matched/original

func findSmallestRegion(regions [][]string, region1 string, region2 string) string {
    parent := make(map[string]string)

    for _, regionList := range regions {
        for i := 1; i < len(regionList); i++ {
            parent[regionList[i]] = regionList[0]
        }
    }

    ancestors1 := make(map[string]bool)
    for region1 != "" {
        ancestors1[region1] = true
        region1 = parent[region1]
    }

    for !ancestors1[region2] {
        region2 = parent[region2]
    }

    return region2
}

Explanation

Algorithm

Построим дерево регионов, где каждый регион указывает на своего родителя.

Используя родительскую информацию, найдем путь от каждого региона до корня.

Найдем последний общий регион в путях двух заданных регионов.

😎