Reconstruct Itinerary - Leetcode Solution

The Reconstruct Itinerary problem on LeetCode requires you to reconstruct the itinerary based on a list of flight tickets.

The input to the problem is a list of flight tickets represented as a list of lists. Each ticket is represented by a list containing the source airport and the destination airport. The first airport in the list is the starting airport.

The output should be a list containing the itinerary in the correct order.

To solve the problem, you can use a recursive approach. Starting at the starting airport, you can find all the destinations from the current airport and recursively try to find an itinerary from each destination.

To optimize the solution, you can use a dictionary to keep track of all the flights and their destinations. This will allow you to quickly find the destinations for a given airport.

Here is the Python code for the solution:

def findItinerary(tickets: List[List[str]]) -> List[str]:
    def visit(airport):
        while flights.get(airport):
            visit(flights[airport].pop(0))
        itinerary.append(airport)
    
    flights = {}
    for start, end in tickets:
        if start not in flights:
            flights[start] = []
        flights[start].append(end)
    for start in flights:
        flights[start].sort()
        
    itinerary = []
    visit('JFK')
    return itinerary[::-1]

The function first creates a dictionary called flights to store all the flights and their destinations. It then sorts the destinations for each airport to ensure that the itinerary is in lexicographic order.

The visit function uses recursion to traverse the flight itinerary. It starts at the current airport and continues to visit the next destination until there are no more destinations left. It then adds the current airport to the itinerary.

Finally, the function calls the visit function starting at the starting airport and returns the itinerary in reverse order to get the correct order.

1