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 ListfindItinerary(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; i0) { // 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; };