1436. Destination City

1. Question

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.

2. Examples

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"

3. 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.

4. References

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/destination-city 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

5. Solutions

class Solution {
  public String destCity(List<List<String>> paths) {
    HashSet<String> set = new HashSet<>();

    for (List<String> lst : paths) {
      set.add(lst.get(0));
    }
    for (List<String> lst : paths) {
      if (!set.contains(lst.get(1))) {
        return lst.get(1);
      }
    }
    return null;
  }
}
Copyright © rootwhois.cn 2021-2022 all right reserved,powered by GitbookFile Modify: 2022-11-26 20:03:31

results matching ""

    No results matching ""