Reconstruct Itinerary

Reconstruct Itinerary

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 from JFK. Thus, the itinerary must begin with JFK.

Note:

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. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets may 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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

package array; import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.PriorityQueue; public class ResonstructIternenary { public List<String> findItinerary(String[][] tickets) { // construct adjacency list, make its adjacency list sorted // make sure it is really a list and not set. use set when it does not allow // duplication //sorted list in java can be priority queue Map<String, PriorityQueue<String>> adl = new HashMap<String, PriorityQueue<String>>(); for (String[] ft : tickets) { PriorityQueue<String> to = adl.get(ft[0]); if (to == null) to = new PriorityQueue<String>();// so every from node has a // queue even it is empty to.add(ft[1]); adl.put(ft[0], to); } //to hold the path LinkedList<String> itinerary = new LinkedList<String>(); dfs(adl, "JFK", itinerary); return itinerary; } /** * depth first traversal following the minimum ordered destinations * remove the destination from adjacency list so that it won't be visited twice * when no further destination to go further, put the destination to the path * * @param adl * @param string * @param itinerary */ private void dfs(Map<String, PriorityQueue<String>> adl, String from, LinkedList<String> itinerary) { while (adl.keySet().contains(from) && adl.get(from).size() > 0) { dfs(adl, adl.get(from).poll(), itinerary); } // it will reach to here after dfs is done, which means reaching to // deepest leaves from current node // the stack of nested calls keeps the order of node visiting. reflect // it by adding to from of list itinerary.addFirst(from); } public static void main(String[] args) { ResonstructIternenary o = new ResonstructIternenary(); String[][] tickets = { { "JFK", "SFO" }, { "JFK", "ATL" }, { "SFO", "JFK" } }; List<String> itinerary = o.findItinerary(tickets); System.out.println(itinerary); } }