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]