Last updated on July 20th, 2024 at 04:10 am
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
Topics
Depth-First Search, Graph
Companies
Level of Question
Hard
![Reconstruct Itinerary LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
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:
![itinerary1 graph](https://i0.wp.com/assets.leetcode.com/uploads/2021/03/14/itinerary1-graph.jpg?w=1400&ssl=1)
Input: tickets = [[“MUC”,”LHR”],[“JFK”,”MUC”],[“SFO”,”SJC”],[“LHR”,”SFO”]]
Output: [“JFK”,”MUC”,”LHR”,”SFO”,”SJC”]
Example 2:
![itinerary2 graph](https://i0.wp.com/assets.leetcode.com/uploads/2021/03/14/itinerary2-graph.jpg?w=1400&ssl=1)
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.
1. 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; } };
2. 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); } }
3. 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(); };
4. 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]