LeetCode Reconstruct Itinerary Solution
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
andtoi
consist of uppercase English letters.fromi != toi
Problem Link: https://leetcode.com/problems/reconstruct-itinerary/
Solution
We want to find a route that uses all flight ticket. The natural instinct is to use a backtracking approach. We can try constructing this route
by greedily selecting the destination (smallest alphabetical destination) from a source,
and when we get stuck, we backtrack to a previous location and search for the other possible routes.
Since we are employing a greedy selection in this backtracking algorithm, the practical runtime should be much faster than the worst-case exponential runtime of backtracking problems.
Implementation
1def findItinerary(tickets: List[List[str]]) -> List[str]:
2 # set up flights graph, and unvisited counter for each (src, dst)
3 flights = defaultdict(list)
4 unvisited = defaultdict(int)
5 tickets.sort() # sort tickets so selection is greedy
6 for src, dst in tickets:
7 flights[src].append(dst)
8 unvisited[(src, dst)] += 1
9
10 def backtracking(src, route, unvisited):
11 if len(route) == len(tickets) + 1: # found solution
12 return True
13 for dst in flights[src]:
14 if unvisited[(src, dst)]: # take flight
15 unvisited[(src, dst)] -= 1 # visit (src, dst)
16 route.append(dst) # update route
17 if backtracking(dst, route, unvisited):
18 return True
19 route.pop() # revert route
20 unvisited[(src, dst)] += 1 # unvisit (src, dst)
21 return False
22
23 route = ['JFK']
24 backtracking('JFK', route, unvisited)
25 return route