最小公共区域

/*
 * Leetcode 1257: Smallest Common Region
 * 
 * Given a list of regions where the first region in each list includes all other regions in that list, find the smallest region that contains both given regions.
 * 
 * Steps to solve the problem:
 * 1. Use a map to keep track of each region and its parent region.
 * 2. Find the path from each given region to the root region and store it in a set.
 * 3. Traverse the path from one region and check for the first common region in the set of the other region.
 */

import java.util.*;
import java.util.stream.Collectors;

public class SmallestCommonRegionStream {
    public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
        Map<String, String> parentMap = regions.stream()
            .flatMap(list -> list.subList(1, list.size()).stream().map(region -> new AbstractMap.SimpleEntry<>(region, list.get(0))))
            .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

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

        while (region2 != null) {
            if (pathToRoot1.contains(region2)) {
                return region2;
            }
            region2 = parentMap.get(region2);
        }

        return null; // Should never reach here if input is valid
    }

    public static void main(String[] args) {
        List<List<String>> regions = Arrays.asList(
            Arrays.asList("Earth", "North America", "South America"),
            Arrays.asList("North America", "United States", "Canada"),
            Arrays.asList("United States", "California", "Texas"),
            Arrays.asList("Canada", "Ontario", "Quebec"),
            Arrays.asList("South America", "Brazil", "Argentina")
        );
        SmallestCommonRegionStream solver = new SmallestCommonRegionStream();
        System.out.println(solver.findSmallestRegion(regions, "California", "Quebec")); // Output: North America
    }
}