Problem Description
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 <= 300tickets[i].length == 2fromi.length == 3toi.length == 3fromiandtoiconsist of uppercase English letters.fromi != toi
The description was taken from https://leetcode.com/problems/reconstruct-itinerary/.
Problem Solution
#O(V^E) Time, O(V+E) Space
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
adjacency, output = {}, ["JFK"]
for node, neighbor in sorted(tickets):
if node not in adjacency:
adjacency[node] = [neighbor]
else:
adjacency[node].append(neighbor)
def backtrack(start:str) -> bool:
if len(output) == len(tickets) + 1:
return True
if start not in adjacency:
return False
for i, neighbor in enumerate(adjacency[start]):
if not neighbor:
continue
original = adjacency[start][i]
adjacency[start][i] = ""
output.append(neighbor)
if backtrack(neighbor):
return True
adjacency[start][i] = original
output.pop()
return False
backtrack("JFK")
return outputProblem Explanation
An easier variation of this problem is All Paths From Source to Target.
The main idea between these two problems is that if we are given a scenario that may require us to generate every combination of paths, then backtracking is typically a good approach to go with.
The two additional requirements that we will need to account for in this question from the previous variation, however, is we will need to try the smallest lexicographically ordered path first so we will need to account for cycles since we will try different combinations of flights.
The first requirement is simple enough, we'll just sort the input adjacency list to prioritize our flight plans.
The second one can be handled by removing a flight we're extending a DFS path on from the current adjacency list so that we don't retry that flight further down the path.
Let's start by initializing our adjacency list and our output.
Each output will always begin from "JFK", so we will initialize our output with that value.
adjacency, output = {}, ["JFK"]
Next, for each node and neighbor in the sorted tickets list, if the node is not in the adjacency list yet then we will initialize it there. Otherwise, we will append this additional neighbor to its adjacency list.
for node, neighbor in sorted(tickets):
if node not in adjacency:
adjacency[node] = [neighbor]
else:
adjacency[node].append(neighbor)
Now we will create our recursive backtrack function.
Once we get the first valid flight combination, we are going to want to terminate early so that we don't try anymore. We can do this by returning a boolean value so that if a child recursive call was valid, we can return instead of continuing the DFS.
def backtrack(start:str) -> bool:
We'll know if a flight is valid by seeing if the length of the output is equal to the length of the tickets, plus one to include the JFK airport source node.
If that is the case, we will return true.
if len(output) == len(tickets) + 1:
return True
We'll also know if the current path is invalid by whether the current starting node has no other airport destinations within its adjacency list and we didn't just return true from the previous condition.
That would mean we are at a dead-end and haven't constructed a proper itinerary through the combination of flights we took within this current DFS path.
If this is the case, we'll return false.
if start not in adjacency:
return False
Otherwise, we will go through our connected flights within the current node adjacency list and try these paths in order since we sorted them at the beginning of the solution.
for i, neighbor in enumerate(adjacency[start]):
If the current neighbor is empty then we already took this path previously within the current DFS path. If this is the case then we will continue to try the next flight.
if not neighbor:
continue
Otherwise, we will try placing this neighboring flight within the current DFS combination.
We'll save its value, set its index to empty to avoid cycles, append its value to the output and continue down the DFS path that this placement leads to.
original = adjacency[start][i]
adjacency[start][i] = ""
output.append(neighbor)
If the path returns true, however, then we don't want to try any more combinations so we will terminate this DFS by returning true as well.
if backtrack(neighbor):
return True
If it doesn't, then we will backtrack on our choice by putting this neighbor back into our adjacency list from where we took it and removing it from the output so that we can try the next neighbor.
adjacency[start][i] = original
output.pop()
If we tried each neighbor then that means there is a dead-end flight combination higher up the recursive tree from the path we got this starting node from.
We will return false in this case so that a different path is tried higher up the recursive tree.
return False
Now that we have our adjacency list made and our backtrack function built, we'll just need to make the initial call on the JFK airport and return the output.
backtrack("JFK")
return output