Reconstruct Itinerary

Description

Assume we have an array of airline tickets represented as pairs of departure and arrival airports like [from, to]. We have to reconstruct the itinerary in order. All tickets belong to a man who departs from a specified location, e.g., JFK. Therefore, the itinerary must begin with JFK. There might be multiple valid itineraries; you must return the itinerary with the smallest lexical order.

Constraints

Consider the following constraints:

• 1 <= tickets.length <= 300
• tickets[i].length must be 2.
• $from_i.length$, $to_i.length$ == 3
• $from_i$ and $to_i$ consist of uppercase English letters.
• Specified departure must be the start point of itinerary.
• $from_i$ and $to_i$ would not be equal.
• Must use all the tickets but only once.

Let’s try to understand the problem with the help of an example: