# 332. Reconstruct Itinerary



這算是比較特別的 backtracking&#x20;

資料結構現在要改成用  Map\<String, Map\<String, Integer>> graph

backtracking -> remove node, add node

才會過, 不然最後一個 test case 都會 TLE (額外用一個 used map boolean array 的話）



T: O(E^d) ,  E number of filghts (edges), d is the branch numbers of each backtracking

S: O(E), E number of filghts (edges), map needs from -> to

````java
```java
class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, Map<String, Integer>> graph = buildGraph(tickets);
        return dfs("JFK", graph); // start point is "JFK"
    }
    private List<String> dfs(String start, Map<String, Map<String, Integer>> graph) {
        if (graph.isEmpty()) { // when no nodes on graph, just return with start
            return new ArrayList<>(Arrays.asList(start));
        }
        List<String> next = new ArrayList<>(graph.getOrDefault(start, new HashMap<>()).keySet());
        Collections.sort(next); // sort (for smallest lexical order)

        for (String nxt : next) {
            removeNode(start, nxt, graph); // backtracking
            List<String> result = dfs(nxt, graph);
            addNode(start, nxt, graph); // backtracking

            if (result != null) { // always add start in the beginning
                result.add(0, start);
                return result;
            }
        }
        return null;
    }

    private Map<String, Map<String, Integer>> buildGraph(List<List<String>> tickets) {
        Map<String, Map<String, Integer>> graph = new HashMap<>();
        for (List<String> t : tickets) {
            String from = t.get(0);
            String to = t.get(1);
            addNode(from, to, graph);
        }
        return graph;
    }
    private void addNode(String from, String to, Map<String, Map<String, Integer>> graph) {
        graph.putIfAbsent(from, new HashMap<>());
        Map<String, Integer> map = graph.get(from);
        map.put(to, map.getOrDefault(to, 0) + 1);
    }
    private void removeNode(String from, String to, Map<String, Map<String, Integer>> graph) {
        Map<String, Integer> map = graph.get(from);
        map.put(to, map.getOrDefault(to, 0) - 1);
        if (map.get(to) == 0) {
            map.remove(to);
        }
        if (graph.get(from).isEmpty()) {
            graph.remove(from);
        }
    }
}
```
````

why 這個解法可以過呢？

因為最後一個 tes case, 其實充滿了“重複的 flights (from -> to)”

<figure><img src="https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FqlHgsWEsNDoFR0mzYFCu%2Fimage.png?alt=media&#x26;token=424432ad-2763-48d8-96fd-8c58d65f6b0f" alt=""><figcaption></figcaption></figure>

所以其實用了一個 Ｍap\<from, Map\<to, count>>

可以大幅減少重複 case 去計算, 以 "ATL", "AAA" 重複了這麼多次, 我們只需要 add, remove backtracking 一次就可以達到效果



如果是用 Map\<key, Boolean\[]> ->如果 "ATL", "AAA" 重複了100次, 這樣要 backtracking 100次

效果差很多
