Skip to content

Latest commit

 

History

History
35 lines (21 loc) · 1.59 KB

sol.md

File metadata and controls

35 lines (21 loc) · 1.59 KB
Raw
  1. Create a map graph to store the adjacency list of the graph, where the keys are the airports and the values are priority queues of the next airports that can be visited from the current airport.
  2. Iterate over the tickets list and add each ticket to the graph map.
  3. Create a linked list itinerary to store the itinerary.
  4. Call the dfs() function with the starting airport, the graph map, and the itinerary linked list.

The dfs() function works recursively to find a path from the current airport to the end of the itinerary. It does this by repeatedly removing the next airport from the priority queue and calling itself on that airport. When the priority queue is empty, the function adds the current airport to the itinerary linked list.

Example:

Consider the following input:

tickets = [[["JFK", "SFO"], ["JFK", "ATL"], ["SFO", "ATL"], ["ATL", "JFK"]]]

The output is ["JFK", "ATL", "JFK", "SFO"].

Explanation:

The graph map after the iteration over the tickets list is as follows:

graph = { "JFK": ["ATL", "SFO"], "ATL": ["JFK"], "SFO": ["ATL"] }

The dfs() function is called with the starting airport "JFK" as follows:

dfs("JFK", graph, itinerary);

The dfs() function will recursively call itself on the next airports in the priority queue of "JFK", which are "ATL" and "SFO". The dfs() function will eventually reach the end of the itinerary and return. The itinerary linked list will then contain the following airports in order:

["JFK", "ATL", "JFK", "SFO"]

Therefore, the output of the findItinerary() function is ["JFK", "ATL", "JFK", "SFO"].