_1257.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.ArrayList;
importjava.util.HashMap;
importjava.util.List;
importjava.util.Map;

publicclass_1257 {
publicstaticclassSolution1 {
publicStringfindSmallestRegion(
List<List<String>> regions, Stringregion1, Stringregion2) {
Map<String, String> childToParent = newHashMap<>();
for (List<String> region : regions) {
for (inti = 1; i < region.size(); i++) {
Stringparent = region.get(0);
Stringchild = region.get(i);
childToParent.put(child, parent);
 }
 }
List<String> path1 = findPath(childToParent, region1);
List<String> path2 = findPath(childToParent, region2);
inti = path1.size() - 1;
intj = path2.size() - 1;
for (; i >= 0 && j >= 0; ) {
if (path1.get(i).equals(path2.get(j))) {
i--;
j--;
 } else {
if (i == path1.size() - 1) {
returnpath1.get(i);
 } else {
returnpath1.get(i + 1);
 }
 }
 }
if (i < 0) {
returnpath1.get(0);
 } else {
returnpath2.get(0);
 }
 }

privateList<String> findPath(Map<String, String> childToParent, Stringleaf) {
List<String> path = newArrayList<>();
do {
path.add(leaf);
if (childToParent.containsKey(leaf)) {
leaf = childToParent.get(leaf);
 } else {
break;
 }
 } while (true);
returnpath;
 }
 }
}