Python solution with detailed explanation


  • 0
    G

    Solution with detailed explanation https://discuss.leetcode.com/topic/76788/python-solution-with-detailed-explanation

    Reconstruct Itinerary https://leetcode.com/problems/reconstruct-itinerary/

    An Euler path is a path that uses every edge of a graph exactly once. An Euler path starts and ends at different vertices.

    • First build a graph as a dictionary with key as vertex and value as list of edges with edge_id.
    • Now the algorithm to find the Euler path is simple backtracking DFS.
    • Note the Euler path may have cycles - Example 2 shows that. And Euler path allows an edge to be visited just once. Hence we will use edge_seen set to mark the edges visited. We will not mark vertices since we can visit vertices multiple times - cycles are allowed.
    • We start with the first departure - JFK.
    • We then find all the nbr,edge_id we can go to. We choose an edge that has not been visited before.
    • Before we do a DFS, we add this to an edge_seen set and add to so_far
    • touw - implements DFS and returns True when a path is found. We prune out search at that point.
    class Solution(object):
        def build_graph(self, tickets):
            g, ticket_id = {}, 0
            for trip in tickets:
                v, w = trip[0], trip[1]
                g.setdefault(v, [])
                g[v].append((w, ticket_id))
                ticket_id = ticket_id + 1
            for k in g:
                g[k].sort(key=lambda x:x[0])
            return g
        
        def findItinerary(self, tickets):
            """
            :type tickets: List[List[str]]
            :rtype: List[str]
            """
            g = self.build_graph(tickets)
            tickets_used, itenary = set([]), ["JFK"]
            self.tour(g, itenary, tickets_used, len(tickets)+1)
            return itenary
        
        def tour(self, g, itenary, tickets_used, N):
            if len(itenary) == N:
                return True
            else:
                s = itenary[-1]
                if s in g:
                    candidates = ((nbr, ticket_id) for nbr, ticket_id in g[s] if ticket_id not in tickets_used)
                    for nbr, ticket_id in candidates:
                        tickets_used.add(ticket_id)
                        itenary.append(nbr)
                        if self.tour(g, itenary, tickets_used, N):
                            return True
                        itenary.pop()
                        tickets_used.remove(ticket_id)
                return False
    

Log in to reply
 

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