Repository navigation
Expand file tree
/
Copy pathProblem1436.java
More file actions
97 lines (76 loc) · 2.67 KB
/
Copy pathProblem1436.java
File metadata and controls
97 lines (76 loc) · 2.67 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/*
You are given the array paths, where paths[i] = [cityAi, cityBi] means there
exists a direct path going from cityAi to cityBi. Return the destination city,
that is, the city without any path outgoing to another city.
It is guaranteed that the graph of paths forms a line without any loop,
therefore, there will be exactly one destination city.
Example 1:
Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo"
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is
the destination city.
Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".
Example 2:
Input: paths = [["B","C"],["D","B"],["C","A"]]
Output: "A"
Explanation: All possible trips are:
"D" -> "B" -> "C" -> "A".
"B" -> "C" -> "A".
"C" -> "A".
"A".
Clearly the destination city is "A".
Example 3:
Input: paths = [["A","Z"]]
Output: "Z"
Constraints:
1 <= paths.length <= 100
paths[i].length == 2
1 <= cityAi.length, cityBi.length <= 10
cityAi != cityBi
All strings consist of lowercase and uppercase English letters and the space
character.
*/
package leetcode;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Problem1436 {
public static void main(String[] args) {
List<List<String>> paths = List.of(
List.of("London", "New York"),
List.of("New York", "Lima"),
List.of("Lima", "Sao Paulo"));
System.out.println("The destination city is " + destCity(paths));
paths = List.of(
List.of("B", "C"),
List.of("D", "B"),
List.of("C", "A"));
System.out.println("The destination city is " + destCity(paths));
paths = List.of(
List.of("A", "Z"));
System.out.println("The destination city is " + destCity(paths));
}
/**
* Returns the destination city, that is, the city without any path outgoing
* to another city.
*
* @param paths The list of paths.
* @return The destination city.
*/
public static String destCity(final List<List<String>> paths) {
// Create a map to store the paths
Map<String, String> map = new HashMap<>();
// Iterate through the paths and add them to the map
for (List<String> path : paths) {
map.put(path.get(0), path.get(1));
}
// Start with the first city in the first path
String city = paths.get(0).get(0);
// Traverse the map until we reach a city without any outgoing path
while (map.containsKey(city)) {
city = map.get(city);
}
// Return the destination city
return city;
}
}