Reconstruct Itinerary
Hard · Graphs · Depth-First Search · Graph · Eulerian Circuit
Problem
You are given a traveller’s airline tickets, each one [from, to]. The traveller starts at "JFK", and the tickets fit together into one trip that uses every ticket exactly once. Rebuild that trip and return the airports in the order they are visited.
If several trips use all the tickets, return the one that is smallest in lexicographic order: compare the lists airport by airport, and the first difference decides. The tests always have at least one valid trip. A ticket can appear more than once, and each copy is used once.
Flying to the alphabetically smallest destination every time is not enough. It can strand you at an airport with tickets still unused.
Examples
Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] Output: ["JFK","MUC","LHR","SFO","SJC"]
Each airport has only one ticket out of it, so there is only one way to chain them from JFK.
Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
JFK, SFO, ATL, JFK, ATL, SFO also uses every ticket, but at the second airport ATL comes before SFO.
Constraints
- 1 <= len(tickets) <= 300
- from and to are three uppercase letters, and from != to
- at least one trip from "JFK" uses every ticket
Approaches
- Backtracking in alphabetical order — time exponential in the worst case, space O(E)
Related problems
Start free on Cariara · Coding problems · System design studio
