Finding Travel Itinerary Explanation

We will write a function to find possible travel itineraries using flight tickets.

This process will be implemented using recursion and Depth-First Search (DFS).

Function Implementation

1. Initialize the Graph:

   • Create a graph using the departure and destination of each ticket.

   • This graph stores a list of all destinations reachable from each airport.

2. Sort Tickets:

   • Sort tickets departing from each airport in reverse order. This allows the DFS to explore the lexicographically smallest route first.

3. Implement the DFS Function:

   • Define a recursive function dfs that explores all possible routes starting from the current airport.

   • After exploration, add the route to the route list.

4. Calculate the Final Route:

   • Initiate the dfs function starting from the JFK airport.

   • Since routes are stored in reverse order, reverse the list before returning the final result.

Optimal Solution

def solution(tickets):
    graph = {}  # Initialize the graph
    for start, end in tickets:
        graph.setdefault(start, []).append(end)  # Add departure and destination pairs
        graph.setdefault(end, [])

    # Sort tickets
    for airport in graph:
        graph[airport].sort(reverse=True)

    route = []  # Store the route

    # DFS function
    def dfs(airport):
        while graph[airport]:
            dfs(graph[airport].pop())  # Move to the next destination
        route.append(airport)  # Add to route

    dfs("JFK")  # Start from 'JFK'
    return route[::-1]  # Return the final route

Example Usage

Example Input/Output

print(solution([["JFK", "SFO"], ["LAX", "MIA"], ["SFO", "LAX"]]))  # Output: ["JFK", "SFO", "LAX", "MIA"]

In this example, the task is to find a possible travel itinerary using the given tickets. The tickets are ["JFK", "SFO"], ["LAX", "MIA"], ["SFO", "LAX"], representing the departure and destination. The goal is to find the lexicographically smallest route using all the tickets.

The function solution finds the following itinerary using these tickets: ["JFK", "SFO", "LAX", "MIA"]. This route uses all the tickets and is the smallest in lexicographical order.

The route is created by departing from "JFK" to "SFO", then continuing to "LAX" and finally arriving at "MIA". This satisfies the given conditions, so the function returns this route.

Want to learn more?

Join CodeFriends Plus membership or enroll in a course to start your journey.

Learn moreSign In