Problem
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.
Constraints:
1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi
andtoi
consist of uppercase English letters.fromi != toi
Solution
/**
* @param {string[][]} tickets
* @return {string[]}
*/
var findItinerary = function(tickets) {
tickets.sort((a, b) => (a[1] === b[1] ? 0 : (a[1] < b[1] ? -1 : 1)));
var map = {};
for (var i = 0; i < tickets.length; i++) {
if (!map[tickets[i][0]]) map[tickets[i][0]] = [];
map[tickets[i][0]].push(tickets[i][1]);
}
var itinerary = [];
dfs('JFK', map, itinerary);
return itinerary.reverse();
};
var dfs = function(airport, map, itinerary) {
while (map[airport]?.length) {
dfs(map[airport].shift(), map, itinerary);
}
itinerary.push(airport);
};
Explain:
nope.
Complexity:
- Time complexity : O(n * log(n)).
- Space complexity : O(n).