332. Reconstruct Itinerary

這算是比較特別的 backtracking

資料結構現在要改成用 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
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)”

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

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

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

效果差很多