# 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

``````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 {
List<String> destList = new LinkedList<String>();
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;
boolean ret = backtracking(dest, route);
route.pollLast();
bitmap[i] = false;

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

return false;
}
}``````

Last updated