# 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
```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="/files/sD1MJMc9pq0zbmPPb36o" alt=""><figcaption></figcaption></figure>

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

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

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

效果差很多


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/332.-reconstruct-itinerary.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.