Skip to content

Commit 65d9ce8

Browse files
fishercoder1534fishercoder1534
committed
add 1257
1 parent 804505b commit 65d9ce8

File tree

3 files changed

+159
-0
lines changed

3 files changed

+159
-0
lines changed

‎README.md

+1
Original file line numberDiff line numberDiff line change
@@ -373,6 +373,7 @@ _If you like this project, please leave me a star._ ★
373373
|1261|[Find Elements in a Contaminated Binary Tree](https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1261.java) ||Medium|Tree, HashTable|
374374
|1260|[Shift 2D Grid](https://leetcode.com/problems/shift-2d-grid/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1260.java) | [:tv:](https://www.youtube.com/watch?v=9hBcARSiU0s)|Easy||
375375
|1258|[Synonymous Sentences](https://leetcode.com/problems/synonymous-sentences/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1258.java) ||Medium|Backtracking|
376+
|1257|[Smallest Common Region](https://leetcode.com/problems/smallest-common-region/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1257.java) ||Medium|Tree, HashTable, DFS, BFS|
376377
|1252|[Cells with Odd Values in a Matrix](https://leetcode.com/problems/cells-with-odd-values-in-a-matrix/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1252.java) | |Easy||
377378
|1249|[Minimum Remove to Make Valid Parentheses](https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1249.java) | |Medium|String, Stack|
378379
|1243|[Array Transformation](https://leetcode.com/problems/array-transformation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1243.java) | [:tv:](https://www.youtube.com/watch?v=MQ2i4T1l-Gs)|Easy||

‎src/main/java/com/fishercoder/solutions/_1257.java

+55
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.ArrayList;
4+
import java.util.HashMap;
5+
import java.util.List;
6+
import java.util.Map;
7+
8+
public class _1257 {
9+
public static class Solution1 {
10+
public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
11+
Map<String, String> childToParent = new HashMap<>();
12+
for (List<String> region : regions) {
13+
for (int i = 1; i < region.size(); i++) {
14+
String parent = region.get(0);
15+
String child = region.get(i);
16+
childToParent.put(child, parent);
17+
}
18+
}
19+
List<String> path1 = findPath(childToParent, region1);
20+
List<String> path2 = findPath(childToParent, region2);
21+
int i = path1.size() - 1;
22+
int j = path2.size() - 1;
23+
for (; i >= 0 && j >= 0; ) {
24+
if (path1.get(i).equals(path2.get(j))) {
25+
i--;
26+
j--;
27+
} else {
28+
if (i == path1.size() - 1) {
29+
return path1.get(i);
30+
} else {
31+
return path1.get(i + 1);
32+
}
33+
}
34+
}
35+
if (i < 0) {
36+
return path1.get(0);
37+
} else {
38+
return path2.get(0);
39+
}
40+
}
41+
42+
private List<String> findPath(Map<String, String> childToParent, String leaf) {
43+
List<String> path = new ArrayList<>();
44+
do {
45+
path.add(leaf);
46+
if (childToParent.containsKey(leaf)) {
47+
leaf = childToParent.get(leaf);
48+
} else {
49+
break;
50+
}
51+
} while (true);
52+
return path;
53+
}
54+
}
55+
}

‎src/test/java/com/fishercoder/_1257Test.java

+103
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._1257;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import java.util.Arrays;
8+
9+
import static org.junit.Assert.assertEquals;
10+
11+
public class _1257Test {
12+
private static _1257.Solution1 solution1;
13+
14+
@BeforeClass
15+
public static void setup() {
16+
solution1 = new _1257.Solution1();
17+
}
18+
19+
@Test
20+
public void test1() {
21+
assertEquals("North America", solution1.findSmallestRegion(
22+
Arrays.asList(Arrays.asList("Earth", "North America", "South America"),
23+
Arrays.asList("North America", "United States", "Canada"),
24+
Arrays.asList("United States", "New York", "Boston"),
25+
Arrays.asList("Canada", "Ontario", "Quebec"),
26+
Arrays.asList("South America", "Brazil")), "Quebec", "New York"));
27+
}
28+
29+
@Test
30+
public void test2() {
31+
assertEquals("Canada", solution1.findSmallestRegion(
32+
Arrays.asList(Arrays.asList("Earth", "North America", "South America"),
33+
Arrays.asList("North America", "United States", "Canada"),
34+
Arrays.asList("United States", "New York", "Boston"),
35+
Arrays.asList("Canada", "Ontario", "Quebec"),
36+
Arrays.asList("South America", "Brazil")),
37+
"Canada", "Quebec"));
38+
}
39+
40+
@Test
41+
public void test3() {
42+
assertEquals("Earth", solution1.findSmallestRegion(
43+
Arrays.asList(Arrays.asList("Earth", "North America", "South America"),
44+
Arrays.asList("North America", "United States", "Canada"),
45+
Arrays.asList("United States", "New York", "Boston"),
46+
Arrays.asList("Canada", "Ontario", "Quebec"),
47+
Arrays.asList("South America", "Brazil")),
48+
"Canada", "South America"));
49+
}
50+
51+
@Test
52+
public void test4() {
53+
assertEquals("GfAj", solution1.findSmallestRegion(
54+
Arrays.asList(Arrays.asList("zDkA", "GfAj", "lt"),
55+
Arrays.asList("GfAj", "rtupD", "og", "l"),
56+
Arrays.asList("rtupD", "IT", "jGcew", "ZwFqF"),
57+
Arrays.asList("og", "yVobt", "EjA", "piUyQ"),
58+
Arrays.asList("IT", "XFlc", "W", "rB"),
59+
Arrays.asList("l", "GwQg", "shco", "Dub", "KwgZq"),
60+
Arrays.asList("jGcew", "KH", "lbW"),
61+
Arrays.asList("KH", "BZ", "sauG"),
62+
Arrays.asList("sNyV", "WbrP"),
63+
Arrays.asList("oXMG", "uqe"),
64+
Arrays.asList("ALlyw", "jguyA", "Mi"),
65+
Arrays.asList("PnGPY", "Ev", "lI"),
66+
Arrays.asList("wmYF", "xreBK"),
67+
Arrays.asList("x", "dclJ"),
68+
Arrays.asList("JyOSt", "i"),
69+
Arrays.asList("yEH", "UY", "GIwLp"),
70+
Arrays.asList("lbW", "M"),
71+
Arrays.asList("th", "JyOSt", "ALlyw"),
72+
Arrays.asList("ZwFqF", "GDl"),
73+
Arrays.asList("Zqk", "th"),
74+
Arrays.asList("Aa", "wmYF"),
75+
Arrays.asList("nQ", "IOw"),
76+
Arrays.asList("oGg", "x"),
77+
Arrays.asList("pLGYN", "ldb"),
78+
Arrays.asList("XjpeC", "vK", "aaO", "D"),
79+
Arrays.asList("a", "TekG", "zp"),
80+
Arrays.asList("Dub", "PnGPY"),
81+
Arrays.asList("SOvB", "iD", "pLGYN", "Zqk"),
82+
Arrays.asList("bmFhM", "SOvB", "RWsEM", "z"),
83+
Arrays.asList("SAH", "bmFhM"),
84+
Arrays.asList("GEs", "oXMG", "tNJYJ"),
85+
Arrays.asList("zh", "PWeEf"),
86+
Arrays.asList("Mfb", "GEs", "XjpeC", "p"),
87+
Arrays.asList("Sn", "rVIh", "twv", "pYA", "Ywm"),
88+
Arrays.asList("piUyQ", "G", "aTi"),
89+
Arrays.asList("If", "e", "y", "quEA", "sNyV"),
90+
Arrays.asList("XFlc", "Sn", "ftXOZ"),
91+
Arrays.asList("lt", "Q", "fWB", "a", "Wk", "zpqU"),
92+
Arrays.asList("xsUkW", "Cssa", "TgPi", "qx"),
93+
Arrays.asList("sauG", "If", "nK", "HHOr", "yEH", "YWMgF"),
94+
Arrays.asList("shco", "xsUkW"),
95+
Arrays.asList("GwQg", "Mfb", "gr", "S", "nQ"),
96+
Arrays.asList("v", "SAH", "Rjr"),
97+
Arrays.asList("BZ", "v", "zh", "oGg", "WP"),
98+
Arrays.asList("yVobt", "Aa", "lJRmv")
99+
),
100+
"RWsEM", "GfAj"));
101+
}
102+
103+
}

0 commit comments

Comments
 (0)