Solution For Reconstruct Itinerary

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.

Step by Step Implementation For Reconstruct Itinerary

import java.util.*; 

public class Solution {
    public List findItinerary(String[][] tickets) {
        // create a map of the tickets
        Map> map = new HashMap<>();
        for (String[] ticket : tickets) {
            if (!map.containsKey(ticket[0])) {
                map.put(ticket[0], new PriorityQueue<>());
            }
            map.get(ticket[0]).add(ticket[1]);
        }
        // create a list to store the itinerary
        List itinerary = new ArrayList<>();
        // create a stack to keep track of the path
        Stack stack = new Stack<>();
        // start from JFK
        stack.push("JFK");
        // while the stack is not empty
        while (!stack.isEmpty()) {
            // get the top element of the stack
            String airport = stack.peek();
            // if the map contains the airport
            if (map.containsKey(airport)) {
                // get the list of destinations from the map
                PriorityQueue destinations = map.get(airport);
                // if the list of destinations is not empty
                if (!destinations.isEmpty()) {
                    // remove the top destination from the list
                    String dest = destinations.poll();
                    // push the destination to the stack
                    stack.push(dest);
                }
                // if the list of destinations is empty
                else {
                    // add the airport to the itinerary
                    itinerary.add(airport);
                    // remove the airport from the stack
                    stack.pop();
                }
            }
            // if the map does not contain the airport
            else {
                // add the airport to the itinerary
                itinerary.add(airport);
                // remove the airport from the stack
                stack.pop();
            }
        }
        // return the itinerary
        return itinerary;
    }
}

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
All airports are represented by three capital letters (IATA code).
You may assume all tickets form at least one valid itinerary.
One must use all the tickets once and only once.
Example 1:

Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]
Example 2:

Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"].
             But it is larger in lexical order.
             
def findItinerary(tickets):
    # create a map of all the tickets
    # the key is the departure airport
    # the value is a list of all the arrival airports
    ticket_map = collections.defaultdict(list)
    for ticket in tickets:
        ticket_map[ticket[0]].append(ticket[1])
        
    # sort the values in the map in lexical order
    for key in ticket_map:
        ticket_map[key].sort()
        
    # create a list to store the itinerary
    # we will be using a stack to keep track of the airports
    itinerary = []
    stack = ['JFK']
    
    # while the stack is not empty
    while stack:
        # pop the top airport from the stack
        curr = stack.pop()
        # add it to the itinerary
        itinerary.append(curr)
        # if there are any tickets with the current airport as the departure
        if curr in ticket_map:
            # sort the tickets in lexical order
            ticket_map[curr].sort()
            # add all the arrival airports to the stack
            for airport in ticket_map[curr]:
                stack.append(airport)
                
    # return the itinerary in reverse order
    return itinerary[::-1]

var findItinerary = function(tickets) {
    // create a map of all the destinations
    let map = {};
    for (let i = 0; i < tickets.length; i++) {
        let curr = tickets[i];
        if (!map[curr[0]]) {
            map[curr[0]] = [curr[1]];
        } else {
            map[curr[0]].push(curr[1]);
        }
    }
    
    // sort the destinations in alphabetical order
    for (let key in map) {
        map[key].sort();
    }
    
    // create the itinerary
    let itinerary = [];
    let createItinerary = function(curr) {
        while (map[curr] && map[curr].length > 0) {
            createItinerary(map[curr].shift());
        }
        itinerary.unshift(curr);
    };
    
    createItinerary('JFK');
    return itinerary;
};

There are a few key points to this problem:

1) We need to find the Eulerian path in the given graph.
2) The given graph is directed, so we need to find the Hamiltonian path.
3) We need to use the Hierholzer's algorithm to find the Eulerian path.

The code for this solution is as follows:

#include 
#include 
#include 
#include 

using namespace std;

class Solution {
public:
    vector findItinerary(vector> tickets) {
        // Build the graph
        unordered_map> graph;
        for (auto& ticket : tickets) {
            graph[ticket.first].insert(ticket.second);
        }
        
        // Find the Eulerian path
        vector path;
        string curr = "JFK";
        dfs(graph, curr, path);
        return vector(path.rbegin(), path.rend());
    }
    
    void dfs(unordered_map>& graph, string curr, vector& path) {
        while (!graph[curr].empty()) {
            string next = *graph[curr].begin();
            graph[curr].erase(graph[curr].begin());
            dfs(graph, next, path);
        }
        path.push_back(curr);
    }
};

var findItinerary = function(tickets) {
    
    // create a map of all the destinations and their corresponding ticket
    let map = new Map();
    for (let i=0; i 0) {
            // get the next ticket and remove it from the list
            let next = tickets.shift();
            dfs(next);
        }
        // once we reach a destination with no more tickets, we can add it to our itinerary
        itinerary.unshift(curr);
    };
    
    // start from JFK
    dfs('JFK');
    return itinerary;
};