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:

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 form at least one valid itinerary.

Example 1:

Input: 
tickets
 = 
[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: 
["JFK", "MUC", "LHR", "SFO", "SJC"]

Example 2:

Input: 
tickets
 = 
[["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

Actually this is a Hierholtz's algorithm to traverse Eulerian path

(1) Java

Recursive

class Solution {
    public List<String> findItinerary(String[][] tickets) {
        List<String> rst = new LinkedList<>();
        if (tickets == null || tickets.length == 0 || tickets[0].length == 0) {
            return rst;
        }
        Map<String, PriorityQueue<String>> map = new HashMap<>();
        for (String[] ticket : tickets) {
            if (!map.containsKey(ticket[0])) {
                map.put(ticket[0], new PriorityQueue<String>());
            }
            map.get(ticket[0]).offer(ticket[1]);
        }
        dfs("JFK", map, rst);
        return rst;
    }

    private void dfs(String depart, Map<String, PriorityQueue<String>> map, List<String> rst) {
        while (map.containsKey(depart) && map.get(depart).size() > 0) {
            String start = map.get(depart).poll();
            dfs(start, map, rst);
        }
        rst.add(0, depart);
    }
}

Iterative

class Solution {
    public List<String> findItinerary(String[][] tickets) {
        List<String> rst = new LinkedList<>();
        if (tickets == null || tickets.length == 0 || tickets[0].length == 0) {
            return rst;
        }
        Map<String, PriorityQueue<String>> map = new HashMap<>();
        for (String[] ticket : tickets) {
            if (!map.containsKey(ticket[0])) {
                map.put(ticket[0], new PriorityQueue<String>());
            }
            map.get(ticket[0]).offer(ticket[1]);
        }
        Deque<String> stack = new LinkedList<String>();
        stack.push("JFK");
        while (!stack.isEmpty()) {
            while(!stack.isEmpty() && map.containsKey(stack.peek()) && map.get(stack.peek()).size() > 0) {
                String next = map.get(stack.peek()).poll();
                stack.push(next);
            }
            if (!stack.isEmpty()) {
                rst.add(0, stack.poll());
            }
        }
        return rst;
    }
}

(2) Python

(3) Scala