# 332.Reconstruct-Itinerary

## 332. Reconstruct Itinerary

## 题目地址

<https://leetcode.com/problems/reconstruct-itinerary/>

## 题目描述

```
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.

Example 1:
Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

Example 2:
Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"].
             But it is larger in lexical order.
```

## 代码

### Approach #1 Backtracking + Greedy

```java
class Solution {
  HashMap<String, List<String>> flightMap = new HashMap<>();
  HashMap<String, boolean[]> visitBitmap = new HashMap<>();
  int flights = 0;
  List<String> result = null;

  public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> ticket: tickets) {
      String origin = ticket.get(0);
      String dest = ticket.get(1);
      if (this.flightMap.containsKey(origin)) {
        List<String> destList = flightMap.get(origin);
        destList.add(dest);
      } else {
        List<String> destList = new LinkedList<String>();
        destList.add(dest);
        flightMap.put(origin, destList);
      }
    }

    for (Map.Entry<String, List<String>> entry: flightMap.entrySet()) {
      Collections.sort(entry.getValue());
      visitBitmap.put(entry.getKey(), new boolean[entry.getValue().size()]);
    }

    flights = tickets.size();
    LinkedList<String> route = new LinkedList<String>();

    backtracking("JFK", route);
    return result;
  }

  private boolean backtracking(String origin, LinkedList<String> route) {
    if (route.size() == flights + 1) {
      result = (List<String>) route.clone();
        return true;
    }

    if (!this.flightMap.containsKey(origin))        return false;

    int i = 0;
    boolean[] bitmap = visitBitmap.get(origin);

    for (String dest: flightMap.get(origin)) {
      if (!bitmap[i]) {
        bitmap[i] = true;
        route.add(dest);
        boolean ret = backtracking(dest, route);
        route.pollLast();
        bitmap[i] = false;

        if (ret)     return true;
      }
      i++;
    }

    return false;
  }
}
```


---

# 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://wentao-shao.gitbook.io/leetcode/data-structure/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.