Short Python solution DFS + Backtracking


  • 4
    class Solution(object):
        def findItinerary(self, tickets):
    
            def build_graph(tickets):
                G = {}
                for t in tickets:
                    S, E = t
                    G[S] = G.get(S, []) + [E]
                for A in G:
                    G[A].sort(reverse=True)
                    G[A] = deque(G[A])
                return G
            
            def dfs(G, S):
                trip.append(S)
                if len(trip) == length:
                    return True
                if S in G:
                    n, i = len(G[S]), 0
                    while i < n:
                        A = G[S].pop()
                        if dfs(G, A):
                            return True
                        G[S].appendleft(A)
                        i += 1
                trip.pop()
                return False
                
                
            G = build_graph(tickets)
            trip, length = [], len(tickets) + 1
            dfs(G, "JFK")
            return trip

  • 0
    Y

    agave, your solution is absolutely genius. I just shorted in a bit and made it more 'idiomatic':

    from collections import deque,defaultdict
    class Solution(object):
        def findItinerary(self, tickets):
    
            def build_graph(tickets):
                G = defaultdict(list)
                for S, E in tickets:
                    G[S].append(E)
                for A in G:
                    G[A].sort(reverse=True)
                    G[A] = deque(G[A])
                return G
    
            def dfs(G, S):
                trip.append(S)
                if len(trip) == length:
                    return True
                if S in G:
                    queue=G[S]
                    for i in xrange(len(queue)):
                        A = queue.pop()
                        if dfs(G, A):
                            return True
                        queue.appendleft(A)
                trip.pop()
                return False
    
    
            G = build_graph(tickets)
            trip, length = [], len(tickets) + 1
            dfs(G, "JFK")
            return trip

  • 0

    @yigalirani no genius, just plain DFS + backtracking, nothing out of the ordinary...


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.