package com.fishercoder.solutions;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * 332. 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:
 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"].

 All airports are represented by three capital letters (IATA code).

 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.
 */
public class _332 {

    public static class Solution1 {
        /** credit: https://discuss.leetcode.com/topic/36383/share-my-solution */
        public List<String> findItinerary(String[][] tickets) {
            Map<String, PriorityQueue<String>> flights = new HashMap<>();
            LinkedList<String> path = new LinkedList<>();
            for (String[] ticket : tickets) {
                flights.putIfAbsent(ticket[0], new PriorityQueue<>());
                flights.get(ticket[0]).add(ticket[1]);
            }
            dfs("JFK", flights, path);
            return path;
        }

        public void dfs(String departure, Map<String, PriorityQueue<String>> flights,
            LinkedList path) {
            PriorityQueue<String> arrivals = flights.get(departure);
            while (arrivals != null && !arrivals.isEmpty()) {
                dfs(arrivals.poll(), flights, path);
            }
            path.addFirst(departure);
        }
    }
}

@@ -33,95 +33,8 @@
 s;%0A%0A
-import java.util.ArrayList;%0Aimport java.util.Collections;%0Aimport java.util.Comparator;%0A
 impo
@@ -166,1047 +166,8 @@
 e;%0A%0A
-/**%0A * 332. Reconstruct Itinerary%0A *%0A * Given a list of airline tickets represented by pairs of departure and arrival airports %5Bfrom, to%5D,%0A * reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.%0A%0A Note:%0A If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.%0A For example, the itinerary %5B%22JFK%22, %22LGA%22%5D has a smaller lexical order than %5B%22JFK%22, %22LGB%22%5D.%0A%0A All airports are represented by three capital letters (IATA code).%0A%0A You may assume all tickets form at least one valid itinerary.%0A Example 1:%0A tickets = %5B%5B%22MUC%22, %22LHR%22%5D, %5B%22JFK%22, %22MUC%22%5D, %5B%22SFO%22, %22SJC%22%5D, %5B%22LHR%22, %22SFO%22%5D%5D%0A Return %5B%22JFK%22, %22MUC%22, %22LHR%22, %22SFO%22, %22SJC%22%5D.%0A%0A Example 2:%0A tickets = %5B%5B%22JFK%22,%22SFO%22%5D,%5B%22JFK%22,%22ATL%22%5D,%5B%22SFO%22,%22ATL%22%5D,%5B%22ATL%22,%22JFK%22%5D,%5B%22ATL%22,%22SFO%22%5D%5D%0A Return %5B%22JFK%22,%22ATL%22,%22JFK%22,%22SFO%22,%22ATL%22,%22SFO%22%5D.%0A Another possible reconstruction is %5B%22JFK%22,%22SFO%22,%22ATL%22,%22JFK%22,%22ATL%22,%22SFO%22%5D. But it is larger in lexical order.%0A */%0A
 publ
@@ -230,16 +230,27 @@
      /**
+%0A         *
  credit:
@@ -308,16 +308,25 @@
 solution
+%0A        
  */%0A    
@@ -864,16 +864,28 @@
 lights,%0A
+            
         

refactor 332