Last Updated on 2023-12-15 by Clay
Problem
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.
Every city have a unidirectional connection, and the path of connection would walk only one time. So we can find the destination city.
Solution
I used a dictionary to store the city states. If city A is departure, A += 1; If city A is destination, A -= 1.
Finally, we had found the destination city state is -1. Of course you can use SET instead of dictionary.
C++ Sample Code
class Solution {
public:
string destCity(vector<vector<string>>& paths) {
// Init
unordered_map<string, int> counter;
// Count
for (vector<string>& path: paths) {
++counter[path[0]];
--counter[path[1]];
}
// Get the destination
for (auto& it: counter) {
if (it.second == -1) {
return it.first;
}
}
return "";
}
};
Python Sample Code
class Solution:
def destCity(self, paths: List[List[str]]) -> str:
# Init
counter = {}
# Count
for path in paths:
counter[path[0]] = counter.get(path[0], 0) + 1
counter[path[1]] = counter.get(path[1], 0) - 1
# Find the destination
for city in counter:
if counter[city] == -1:
return city