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.
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".
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".
The destination city is the only city that never appears as a starting point in any path. If we collect all cities that have outgoing paths, the destination city will be the one that is never in this set.
classSolution {
public String destCity(List<List<String>> paths) {
Set<String> out =new HashSet<>();
for (List<String> p : paths) out.add(p.get(0));
for (List<String> p : paths) if (!out.contains(p.get(1))) return p.get(1);
return"";
}
}
1
2
3
4
5
6
7
8
classSolution {
fundestCity(paths: List<List<String>>): String {
val out = mutableSetOf<String>()
for (p in paths) out.add(p[0])
for (p in paths) if (p[1] !inout) return p[1]
return"" }
}
1
2
3
4
5
6
7
classSolution:
defdestCity(self, paths: list[list[str]]) -> str:
out = set(p[0] for p in paths)
for p in paths:
if p[1] notin out:
return p[1]
return""
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
impl Solution {
pubfndest_city(paths: Vec<Vec<String>>) -> String {
use std::collections::HashSet;
letmut out = HashSet::new();
for p in&paths {
out.insert(&p[0]);
}
for p in&paths {
if!out.contains(&p[1]) {
return p[1].clone();
}
}
"".to_string()
}
}
1
2
3
4
5
6
7
8
classSolution {
destCity(paths: string[][]):string {
constout=newSet<string>();
for (constpofpaths) out.add(p[0]);
for (constpofpaths) if (!out.has(p[1])) returnp[1];
return'';
}
}