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 fromJFK. Thus, the itinerary must begin withJFK.
  1. 1.
    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"].
  2. 2.
    All airports are represented by three capital letters (IATA code).
  3. 3.
    You may assume all tickets form at least one valid itinerary.
Example 1: tickets=[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] Return["JFK", "MUC", "LHR", "SFO", "SJC"].
Example 2: tickets=[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] Return["JFK","ATL","JFK","SFO","ATL","SFO"]. Another possible reconstruction is["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.
The Idea: This is a eularian path/cycle problem. Our goal is to visit every edge of the graph once, and return to our original position (in our case, which is 'JFK'). The algorithm that I have used to implement this idea is called Hierholzer's Algorithm. More details and discussion here: https://maksimdan.gitbooks.io/ecs122a-algorithm-design-lecture-notes/content/eularian-cycle.html
Complexity: O(|E|) time and O(|E|) space
from collections import defaultdict
class Solution:
def findItinerary(self, tickets):
:type tickets: List[List[str]]
:rtype: List[str]
if not tickets or not tickets[0]:
return []
# build representative graph
g = defaultdict(list)
for _to, _from in tickets:
# now sort to create smallest
# lexicographical itinerary
for _to, _ in g.items():
# maintain an index where the eularian path
# left off
left_off = {}
for _to, _from in tickets:
left_off[_to] = 0
left_off[_from] = 0
itinerary = []
s = ['JFK']
# now find the eularian path
while s:
top = s[-1]
g_index = left_off[top]
g_list = g[top]
if g_index < len(g_list):
left_off[top] = g_index + 1
return list(reversed(itinerary))