Here, We see Reconstruct Itinerary LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Reconstruct Itinerary LeetCode Solution
Table of Contents
Problem Statement
You are given a list of airline tickets
where tickets[i] = [fromi, toi]
represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.
All of the tickets belong to a man who departs from "JFK"
, thus, the itinerary must begin with "JFK"
. 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"]
.
You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.
Example 1:
Input: tickets = [[“MUC”,”LHR”],[“JFK”,”MUC”],[“SFO”,”SJC”],[“LHR”,”SFO”]]
Output: [“JFK”,”MUC”,”LHR”,”SFO”,”SJC”]
Example 2:
Input: tickets = [[“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.
Reconstruct Itinerary LeetCode Solution C++
class Solution {
public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
unordered_map<string, vector<string>> graph;
for (auto& ticket : tickets) {
graph[ticket[0]].push_back(ticket[1]);
}
for (auto& [_, destinations] : graph) {
sort(destinations.rbegin(), destinations.rend());
}
vector<string> itinerary;
function<void(const string&)> dfs = [&](const string& airport) {
while (!graph[airport].empty()) {
string next = graph[airport].back();
graph[airport].pop_back();
dfs(next);
}
itinerary.push_back(airport);
};
dfs("JFK");
reverse(itinerary.begin(), itinerary.end());
return itinerary;
}
};
Reconstruct Itinerary LeetCode Solution Java
class Solution {
public List<String> findItinerary(List<List<String>> tickets) {
Map<String, PriorityQueue<String>> graph = new HashMap<>();
for (List<String> ticket : tickets) {
graph.putIfAbsent(ticket.get(0), new PriorityQueue<>());
graph.get(ticket.get(0)).add(ticket.get(1));
}
LinkedList<String> itinerary = new LinkedList<>();
dfs("JFK", graph, itinerary);
return itinerary;
}
private void dfs(String airport, Map<String, PriorityQueue<String>> graph, LinkedList<String> itinerary) {
PriorityQueue<String> nextAirports = graph.get(airport);
while (nextAirports != null && !nextAirports.isEmpty()) {
dfs(nextAirports.poll(), graph, itinerary);
}
itinerary.addFirst(airport);
}
}
Code language: JavaScript (javascript)
Reconstruct Itinerary Solution JavaScript
var findItinerary = function(tickets) {
const graph = {};
for (const [src, dst] of tickets) {
if (!graph[src]) graph[src] = [];
graph[src].push(dst);
}
for (const key in graph) {
graph[key].sort().reverse();
}
const itinerary = [];
function dfs(airport) {
while (graph[airport] && graph[airport].length > 0) {
dfs(graph[airport].pop());
}
itinerary.push(airport);
}
dfs("JFK");
return itinerary.reverse();
};
Code language: JavaScript (javascript)
Reconstruct Itinerary Solution Python
class Solution(object):
def findItinerary(self, tickets):
graph = defaultdict(list)
for src, dst in sorted(tickets, reverse=True):
graph[src].append(dst)
itinerary = []
def dfs(airport):
while graph[airport]:
dfs(graph[airport].pop())
itinerary.append(airport)
dfs("JFK")
return itinerary[::-1]