Reconstruct Itinerary - LeetCode
You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it. All of the tickets belong to a man who departs from “JFK”, thus, the itinerary must begin with “JFK”. 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"].You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.
Example 1:
Input: tickets = [[“MUC”,“LHR”],[“JFK”,“MUC”],[“SFO”,“SJC”],[“LHR”,“SFO”]] Output: [“JFK”,“MUC”,“LHR”,“SFO”,“SJC”]
Example 2:
Input: tickets = [[“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.
Constraints:
1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi and toi consist of uppercase English letters.
fromi != toi
- code very slow, as we need to use deepcopy to track the left tickets! new graph should be a deepcopy, not just copy
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
graph = defaultdict(list)
for start, end in tickets:
graph[start].append(end)
for start, trip in graph.items():
trip.sort()
self.res = []
def dfs(cur, path, graph):
if len(path) == len(tickets) + 1:
self.res = path
return True
neis = graph[cur]
for nei in neis:
newgraph = copy.deepcopy(graph)
newgraph[cur].remove(nei)
res = dfs(nei, path + [nei], newgraph)
if res: return True
return False
dfs("JFK", ["JFK"], graph)
return self.res
-code wrongly found all path, why it’s wrong? It will get all path, and update it to the last one. We need to truly return from the recursion the first time when we find a path.
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
graph = defaultdict(list)
for start, end in tickets:
graph[start].append(end)
self.visited = {}
for start, trip in graph.items():
trip.sort()
self.visited[start] = [False] * len(trip)
self.res = []
# for k,v in graph.items():
# print(k,v)
def dfs(cur, path):
if len(path) == len(tickets) + 1:
# print(path)
self.res = path
return
for i in range(len(graph[cur])):
if not self.visited[cur][i]:
self.visited[cur][i] = True
dfs(graph[cur][i], path + [graph[cur][i]])
self.visited[cur][i] = False
dfs("JFK", ["JFK"])
return self.res
- code Backtracking + Greedy
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
graph = defaultdict(list)
for start, end in tickets:
graph[start].append(end)
self.visited = {}
for start, trip in graph.items():
trip.sort()
self.visited[start] = [False] * len(trip)
self.res = []
def dfs(cur, path):
if len(path) == len(tickets) + 1:
self.res = path
return True # not only return, but return True
for i in range(len(graph[cur])):
if not self.visited[cur][i]:
self.visited[cur][i] = True
res = dfs(graph[cur][i], path + [graph[cur][i]])
self.visited[cur][i] = False
if res: return True # make sure jump out once found the first res
return False # unecessary
dfs("JFK", ["JFK"])
return self.res
- code Hierholzer’s Algorithm
class Solution {
LinkedList<String> res = new LinkedList();
HashMap<String, LinkedList<String>> trips = new HashMap();
public List<String> findItinerary(List<List<String>> tickets) {
for (List<String> ticket: tickets){
String start = ticket.get(0);
String end = ticket.get(1);
if (!trips.containsKey(start)){
LinkedList<String> ends = new LinkedList();
ends.add(end);
trips.put(start, ends);
}else{
List<String> ends = trips.get(start);
ends.add(end);
}
}
// for (String key: trips.keySet()){
// Collections.sort(trips.get(key));
// }
trips.forEach((key, value) -> Collections.sort(value));
dfs("JFK");
return res;
}
protected void dfs(String start){
while (trips.containsKey(start) && !trips.get(start).isEmpty()){
String nei = trips.get(start).pollFirst();
dfs(nei);
}
res.offerFirst(start);
}
}