All problems

Reconstruct Itinerary

Hard · graph traversal

You hold a pile of one-way flight tickets. Each ticket is a pair [from, to] of airport codes (one to three capital letters). You are standing at the airport start.

Plan a trip that begins at start and uses every ticket exactly once, each ticket flown from its from airport to its to airport. Tickets can be used in any order, as long as each flight starts where the previous one landed. You may pass through the same airport many times, and two tickets may be identical.

If more than one trip works, return the one that is smallest in dictionary order. Compare two trips airport by airport from the beginning: at the first position where they differ, the trip with the alphabetically smaller code is the smaller trip (codes are compared as plain strings, so "ABC" comes before "ABD", and "AB" before "ABC").

Return the trip as the list of airports visited, including start as the first entry, so it has one more entry than there are tickets. At least one valid trip is guaranteed to exist.

Examples

Example 1

Input: tickets = [["AMS", "OSL"], ["OSL", "CPH"], ["CPH", "ARN"]], start = "AMS"

Output: ["AMS", "OSL", "CPH", "ARN"]

The tickets form a single chain, so there is only one order.

Example 2

Input: tickets = [["HEL", "OSL"], ["ARN", "HEL"], ["HEL", "ARN"]], start = "HEL"

Output: ["HEL", "ARN", "HEL", "OSL"]

From HEL both ARN and OSL are possible, and "ARN" is smaller. After returning to HEL the last ticket goes to OSL.

Example 3

Input: tickets = [["ABC", "BCD"], ["ABC", "CDE"], ["CDE", "ABC"]], start = "ABC"

Output: ["ABC", "CDE", "ABC", "BCD"]

"BCD" is the smaller first stop, but it has no onward ticket, so using it first would leave the other two tickets unused. The trip has to visit CDE first.

Constraints