Practice/Pinterest/Leetcode 332. Reconstruct Itinerary

Leetcode 332. Reconstruct Itinerary

CodingMust

Problem

You are tasked with planning a complete flight itinerary given a collection of airline tickets. Each ticket is represented as a pair of airport codes [origin, destination] indicating a one-way flight from the origin to the destination airport.

Your journey must begin at "JFK" airport and use every single ticket exactly once. If multiple valid itineraries exist that satisfy these conditions, you must return the one that comes first in lexicographical (alphabetical) order.

The itinerary should be returned as an ordered list of airport codes representing the sequence of airports visited.

Requirements

1. The itinerary must start at "JFK"
2. Every ticket must be used exactly once
3. Among all valid itineraries, return the lexicographically smallest one
4. All airport codes are uppercase three-letter strings
5. A valid solution is guaranteed to exist

Constraints

• 1 ≤ tickets.length ≤ 300
• tickets[i].length == 2
• Each airport code consists of exactly 3 uppercase English letters
• At least one ticket starts from "JFK"
• The input always has a valid itinerary

Examples

Example 1:

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] Output: ["JFK","MUC","LHR","SFO","SJC"] Explanation: Starting from JFK, we travel to Munich (MUC), then London (LHR), then San Francisco (SFO), and finally San Jose (SJC), using all four tickets.

Example 2:

Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] Output: ["JFK","ATL","JFK","SFO","ATL","SFO"] Explanation: From JFK we have two choices: SFO or ATL. We choose ATL (lexicographically smaller). This path eventually uses all tickets and forms a valid itinerary.

Example 3:

Input: tickets = [["JFK","ATL"]] Output: ["JFK","ATL"] Explanation: With a single ticket, the itinerary simply goes from JFK to ATL.