Reconstruct The Single Valid Itinerary
You hold a pile of one-way transfer tickets, each from one hop to another. Starting from a fixed origin, use every ticket exactly once to form a single itinerary. When multiple legal itineraries exist, return the lexicographically smallest one.
Problem
Given a list of airline tickets [from, to], reconstruct the itinerary that uses all tickets exactly once, starting from 'JFK'. If multiple valid itineraries exist, return the one with the smallest lexical order when read as a single string. A valid itinerary using all tickets is guaranteed.
Input
A list of [from, to] string pairs.
Output
The ordered list of airport codes forming the itinerary.
Constraints
- 1 ≤ tickets.length ≤ 300
- Airport codes are 3 uppercase letters.
- A valid itinerary consuming all tickets exists.
Examples
Example 1
Input
[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output
["JFK","MUC","LHR","SFO","SJC"]
The unique itinerary consuming all four tickets.
Example 2
Input
[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output
["JFK","ATL","JFK","SFO","ATL","SFO"]
Lexically smallest itinerary among the valid options.