LC 0332 [H] Reconstruct Itinerary - ALawliet/algorithms GitHub Wiki
we can't use BFS because it tries to find the optimal/shortest path and we want to make sure we cover all edges at least once
intuitive Fleury's Algorithm: O(E^2)
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
adj = defautldict(list)
tickets.sort() # sort based on the pair
for u, v in tickets:
adj[u].append(v)
res = ['JFK']
def dfs(u):
# edges + 1 (JFK)
if len(res) == len(tickets) + 1:
return True
# no outgoing edges
if u not in adj:
return False
temp = list(adj[u])
for i, v in enumerate(temp):
adj[u].pop(i)
res.append(v)
if dfs(v): return True
# backtrack O((V+E)^2) = O(E^2)
adj[u].insert(i, v)
res.pop()
return False
dfs('JFK')
return res
optimized Euler Path Hierholzer’s Algorithm: O(E)
(adds in order of no more edges then backtracks so we need to reverse sort both the input and the output)
recursive
def findItinerary(self, tickets):
adj = defaultdict(list)
for u, v in sorted(tickets)[::-1]:
adj[u].append(v)
route = []
def dfs(u):
while adj[u]:
v = adj[u].pop()
dfs(v)
route.append(u)
dfs('JFK')
return route[::-1]
iterative
def findItinerary(self, tickets):
adj = defaultdict(list)
for u, v in sorted(tickets)[::-1]:
adj[u].append(v)
route = []
S = ['JFK']
while S:
while adj[S[-1]]: # has neighbors, traverse them
v = adj[S[-1]].pop()
S.append(v) # grab the last neighbor (first lexico after sorting)
route.append(S.pop()) # no more edges, add to result
return route[::-1]