Reconstruct Itinerary

Hard

Graphs

You are given a list of airline tickets, where tickets[i] = [from_i, to_i] is a one-way flight from airport from_i to airport to_i. Airports are three-letter uppercase codes. All of the tickets belong to one traveller who starts at "JFK".

Return the traveller's route as a list of airports, beginning with "JFK", that uses every ticket exactly once. A route that uses m tickets therefore lists m + 1 airports. Identical tickets are separate tickets, and each copy must be used.

At least one valid route is guaranteed to exist. If there are several, return the one that is smallest in lexicographic order when the routes are compared airport by airport (for example, ["JFK", "ATL", "SEA"] comes before ["JFK", "BOS", "ATL"]).

Note that always flying to the alphabetically smallest next airport is not enough on its own: it can strand you at an airport while some tickets are still unused.

Example 1

Input:: tickets = [["JFK", "DEN"], ["JFK", "AUS"], ["DEN", "JFK"], ["AUS", "MIA"]]
Output:: ["JFK", "DEN", "JFK", "AUS", "MIA"]
Explanation: AUS is alphabetically first, but flying there right away leads to MIA, where no ticket leaves, while the DEN tickets are still unused. So the route has to visit DEN and come back first, then finish JFK -> AUS -> MIA.

Example 2

Input:: tickets = [["JFK", "SEA"], ["JFK", "AUS"], ["SEA", "JFK"], ["AUS", "JFK"]]
Output:: ["JFK", "AUS", "JFK", "SEA", "JFK"]
Explanation: Both ["JFK", "AUS", "JFK", "SEA", "JFK"] and ["JFK", "SEA", "JFK", "AUS", "JFK"] use all four tickets. They first differ at the second airport, and AUS < SEA, so the first one is returned.

Example 3

Input:: tickets = [["LAX", "SFO"], ["JFK", "ORD"], ["ORD", "LAX"]]
Output:: ["JFK", "ORD", "LAX", "SFO"]
Explanation: The tickets are not given in travel order. Starting from JFK there is only one way to chain them: JFK -> ORD -> LAX -> SFO.

Constraints

1 ≤ tickets.length ≤ 300
tickets[i].length == 2
from_i and to_i are three uppercase English letters, and from_i != to_i
At least one route uses all of the tickets