332 Reconstruct Itinerary

332. Reconstruct Itinerary

1. Question

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 fromJFK. Thus, the itinerary must begin withJFK.
  1. 1.
    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"].
  2. 2.
    All airports are represented by three capital letters (IATA code).
  3. 3.
    You may assume all tickets form at least one valid itinerary.
Example 1: tickets=[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] Return["JFK", "MUC", "LHR", "SFO", "SJC"].
Example 2: tickets=[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] Return["JFK","ATL","JFK","SFO","ATL","SFO"]. Another possible reconstruction is["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

2. Implementation

(1) DFS
class Solution {
public List<String> findItinerary(String[][] tickets) {
List<String> route = new ArrayList<>();
if (tickets == null || tickets.length == 0) {
return route;
Map<String, PriorityQueue<String>> map = new HashMap<>();
for (String[] ticket : tickets) {
map.putIfAbsent(ticket[0], new PriorityQueue<>());
dfs("JFK", map, route);
return route;
public void dfs(String airport, Map<String, PriorityQueue<String>> map, List<String> route) {
while (map.containsKey(airport) && !map.get(airport).isEmpty()) {
String nextAirport = map.get(airport).remove();
dfs(nextAirport, map, route);
route.add(0, airport);

3. Time & Space Complexity

DFS: 时间复杂度O(n), n为所有的机场个数,空间复杂度O(n)