Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

The title

Paths [I] = [cityA i_ii, cityB i_II] indicates that the paths will go directly from cityA i_II to cityB i_II. Find the final destination of the tour, a city that does not have any route to any other city.

The problem data guarantees that the route diagram will form a circuit with no loops, so that there is exactly one travel destination.

The sample

Enter: Paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"] It starts at London and ends at Sao Paulo. The itinerary for this trip is "London" -> "New York" -> "Lima" -> "Sao Paulo". Input: paths = [[" B ", "C"], [" D ", "B"], [" C ", "A"]] output: "A" explanation: all possible routes are:  "D" -> "B" -> "C" -> "A". "B" -> "C" -> "A". "C" -> "A". "A". Obviously, the end of the trip is "A". Paths = [["A","Z"]]Copy the code

prompt

  • 1 <= paths.length <= 100
  • paths[i].length == 2
  • 1 <= cityA
    i _i     .length, cityB
    i _i     .length <= 10
  • cityA i_ii ! = cityB i_ii
  • All strings consist of uppercase and lowercase English letters and Spaces.

Their thinking

In this simple and difficult topic, I feel that the focus of the investigation is more on the mastery of data structure.

There is one and only one terminus in the Paths, that is, cities that do not have any routes to other cities. In addition to the terminal, all other urban stations have access to cities.

Here we can use Set to save other cities to filter out the terminal.

Code implementation

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

        for(List<String> path : paths){
            set.add(path.get(0));
        }

        for(List<String> path : paths){
            String end = path.get(1);
            if(! set.contains(end)){returnend; }}return ""; }}Copy the code

Complexity analysis

  • Time complexity: O(N)O(N)O(N)
  • Space complexity: O(N)O(N)O(N)

The last

The article has written the bad place, asks the big guys to be generous to give advice, the mistake is the most can let the person grow up, wishes me and the big guy the distance to shorten gradually!

If you feel the article is helpful to you, please click like, favorites, follow, comment four consecutive support, your support is the biggest power of my creation!!

Title source: leetcode-cn.com/problems/de…