Comment on page

# 332.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

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);
} else {
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();
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;