332. Reconstruct Itinerary.md

332. Reconstruct Itinerary

---

leetcode Daily Challenge on June 28, 2020.

leetcode-cn Daily Challenge on August 27, 2020.

---

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.
• One must use all the tickets once and only once.

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.

---

Solution

Eulerian path introduce on wiki.

• mine
  • Java
    • DFS Recursion Runtime: 6 ms, faster than 52.73%, Memory Usage: 40 MB, less than 72.60% of Java online submissions

      // O(N*logN)time 
      // O(N)space
      public List<String> findItinerary(List<List<String>> tickets) {
          List<String> res = new LinkedList<>();
          if (tickets == null || tickets.size() == 0) {
              return res;
          }
          Map<String, List<String>> map = new HashMap<>();
          for (List<String> ticket : tickets) {
              String key = ticket.get(0);
              List<String> list = map.getOrDefault(key, new LinkedList<>());
              list.add(ticket.get(1));
              map.put(key, list);
          }
          map.values().forEach(Collections::sort);
          dfs(map, "JFK", res);
          return res;
      }
      
      void dfs(Map<String, List<String>> map, String next, List<String> temp) {
          List<String> t = map.getOrDefault(next, new LinkedList<>());
          while (t.size() > 0) {
              String dst = t.remove(0);
              dfs(map, dst, temp);
          }
          temp.add(0, next);
      }
      

---

• the most votes

• DFS Iterative Runtime: 7 ms, faster than 42.30%,Memory Usage: 39.8 MB, less than 91.16% of Java online submissions

  // O(N*logN)time 
  // O(N)space
  public List<String> findItinerary(List<List<String>> tickets) {
      Map<String, PriorityQueue<String>> targets = new HashMap<>();
      for (List<String> ticket : tickets)
          targets.computeIfAbsent(ticket.get(0), k -> new PriorityQueue()).add(ticket.get(1));
      List<String> route = new LinkedList();
      LinkedList<String> stack = new LinkedList<>();
      stack.push("JFK");
      while (!stack.isEmpty()) {
          while (targets.containsKey(stack.peek()) && !targets.get(stack.peek()).isEmpty())
              stack.push(targets.get(stack.peek()).poll());
          route.add(0, stack.pop());
      }
      return route;
  }
  

---