1257. Smallest Common Region

T: O(n)
S: O(n)

class Solution {
    public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
        Map<String, String> childToParent = new HashMap<>();
        for (List<String> region : regions) {
            String parent = region.get(0);
            for (int i = 1; i < region.size(); i++) {
                String child = region.get(i);
                childToParent.put(child, parent);
            }
        }
        return findCommonParent(childToParent, region1, region2);
    }
    private String findCommonParent(Map<String, String> childToParent, String region1, String region2) {
        Set<String> set = new HashSet<>();
        String cur = region1;
        while (cur != null) {
            set.add(cur); // add all parents from cur region
            cur = childToParent.get(cur);  // next parent
        }

        cur = region2; // use region2's parent to find in set
        while (cur != null) {
            if (set.contains(cur)) {
                return cur;
            }
            cur = childToParent.get(cur); // next parent
        }
        return null;
    }
}

/***
T: O(n)
S: O(n)

there is another way, no need set, but hard
please see labladon
 */