Reconstruct Itinerary
Given a list of tickets, where each ticket is represented as a pair of departure and arrival airports, reconstruct the itinerary in order. All of the tickets belong to a man who departs from "JFK". Thus, the itinerary must start with "JFK". Additionally, if there are multiple possible itineraries, the itinerary with the smallest lexical order should be chosen.
Constraints:
- If there are multiple routes with the same destination, the route with the smallest lexical order should be chosen.
- All of the tickets belong to a man who departs from "JFK".
- The number of tickets is in the range [1, 30000].
Examples:
Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]
Explanation: The flight itinerary must start with "JFK" and end with "SJC". The route with the smallest lexical order is chosen.
Solutions
Hierholzer's Algorithm
The solution uses Hierholzer's Algorithm to find the Eulerian path in the graph. The graph is represented as a map where each key is an airport and the value is a list of destinations. The algorithm starts from "JFK" and explores the graph using DFS. The route with the smallest lexical order is chosen by sorting the destinations for each airport.
function findItinerary(tickets) {
let map = new Map();
for (let [from, to] of tickets) {
if (!map.has(from)) map.set(from, []);
map.get(from).push(to);
}
for (let from of map.keys()) {
map.get(from).sort();
}
let res = [];
function dfs(from) {
while (map.has(from) && map.get(from).length > 0) {
dfs(map.get(from).shift());
}
res.unshift(from);
}
dfs('JFK');
return res;
}
Follow-up:
What if there are multiple possible itineraries with the same lexical order?
