Course Schedule

Question

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.

Solution

這題乍看之下以為跟 course schedule 一樣，都是 topological sort。一做下去之後發現不得了，原來完全是另外一種不同的算法。這題的核心概念在於 Eulerian path，也就是要在圖裡面找到一條只通過各點一次的路徑。而達成這個目的的算法就是 Hierholzer's algorithm (https://www.youtube.com/watch?v=EEt5_3YmZuM)。他有點類似 backtrack，就是利用 recursion 或者是用 stack 去實現，走到不能再走的時候，把遍歷的點倒著進回要 return 的 path 裡面。倒回去如果遇到可以再往其他路線遍歷的點，就分支出去，等再次走到不能再走，一樣倒著寫回來

    Map<String, PriorityQueue<String>> neighbors;
    List<String> route;
    public List<String> findItinerary(String[][] tickets) {
        route = new ArrayList<String>();
        if (tickets.length == 0 || tickets == null) {
            return route;
        }

        neighbors = new HashMap<String, PriorityQueue<String>>();
        for (String[] ticket : tickets) {
            if (!neighbors.containsKey(ticket[0])) {
                neighbors.put(ticket[0], new PriorityQueue<String>());
            }
            neighbors.get(ticket[0]).add(ticket[1]);
        }
        visit("JFK");
        return route;
    }

    public void visit(String city) {
        while (neighbors.containsKey(city) && !neighbors.get(city).isEmpty()) {
            visit(neighbors.get(city).poll());
        }
        route.add(0, city);
    }