leetcode ReconstructItinerary
z
 2019-04-09 10:36:27   
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
import java.util.*;

public class ReconstructItinerary {
  /**
   * 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:
   *
   * Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
   * Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]
   * Example 2:
   *
   * Input: [["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.
   */
    public static List<String> findItinerary(String[][] tickets) {
      LinkedList<String> res = new LinkedList<>();
      if (tickets.length == 0) return res;

      Map<String, PriorityQueue<String>> map = new HashMap<>();

      for (String[] ticket : tickets) {
        if (!map.containsKey(ticket[0])) {
          map.put(ticket[0], new PriorityQueue<>());
        }
        map.get(ticket[0]).offer(ticket[1]);
      }

      Stack<String> stack = new Stack<>();
      stack.push("a");
      while (!stack.isEmpty()) {
        String top = stack.peek();
        if (!map.containsKey(top) || map.get(top).isEmpty()) {
          res.addFirst(stack.pop());
        } else {
          stack.push(map.get(top).poll());
        }
      }
      return res;
    }
    public static void main(String[] args) {
      String[][] tickets = new String[][]{{"a","b"},{"b", "c"},{"c", "d"},{"c","a"}};
      for (String s: findItinerary(tickets)){
        System.out.println(s);
      }
    }
}