332. Reconstruct Itinerary

Link

Solution

這題就有兩個方式

第一個方式比較直覺，透過map紀錄所有機票能到的地方，根據能到的地方進行排序，再透過DFS來backtrace，若不能把機票用完，就代表有問題，就回到上一個步驟，選擇下一個可能性。

class Solution {
    LinkedList<String> ret;
    Map<String, List<String>> map;
    int total = 0;
    public List<String> findItinerary(List<List<String>> tickets) {
        ret = new LinkedList<>();
        map = new HashMap<>();
        for(List<String> ticket : tickets){
            map.putIfAbsent(ticket.get(0), new LinkedList<String>());
            map.get(ticket.get(0)).add(ticket.get(1));
        }
        for (Map.Entry<String, List<String>> entry : map.entrySet()) {
            Collections.sort(entry.getValue());
        }
        total = tickets.size();
        ret.add("JFK");
        dfs("JFK");
        return ret;
    }
    
    public void dfs(String departure){
        if(map.get(departure) == null) return;
        List<String> adj = map.get(departure);
        for(int i = 0; i < adj.size(); i++){
            String nextDest = adj.get(i);
            adj.remove(i);
            ret.add(nextDest);
            total--;
            dfs(nextDest);
            if(total == 0) return; //能把機票用完
            total++;
            ret.removeLast();
            adj.add(i, nextDest);    
        }
    }
}

第二個方式我來看很tricky，但程式碼意外的簡單 根據調查是套用Hierholzer's algorithm to find a Eulerian path in the graph

能使用這個演算法應該有幾個先決條件

1. 一定存在一個方法可以把所有票用完

class Solution {
    LinkedList<String> ret;
    Map<String, PriorityQueue<String>> map;
    public List<String> findItinerary(List<List<String>> tickets) {
        ret = new LinkedList<>();
        map = new HashMap<>();
        for(List<String> ticket : tickets){
            map.putIfAbsent(ticket.get(0), new PriorityQueue<String>());
            map.get(ticket.get(0)).add(ticket.get(1));
        }
        dfs("JFK");
        return ret;
    }
    
    public void dfs(String departure){
        PriorityQueue<String> adj = map.get(departure);
        while(adj != null && !adj.isEmpty()){
            dfs(adj.poll());
        }
        ret.addFirst(departure);
    }
}