python Backtracking DFS


  • 0
    E

    Group possible destinations by origin city and associate a used/not-used flag. Sort each destination list. Starting with JFK, do a DFS from the currently last city in our path/itinerary, backtracking if we haven't reached our target path length and no options are left.

    class Solution(object):
        def findItinerary(self, tickets):
            """
            :type tickets: List[List[str]]
            :rtype: List[str]
            """
            d={}
            for (a,b) in tickets:
                d.setdefault(a,[]).append([b,False])
            
            for l in d.values():
                l.sort()
            
            path_len = len(tickets)+1
            path=["JFK"]
            def rec():
                if len(path)==path_len:
                    raise Exception("solution")
                else:
                    
                    curr=path[-1]
                    l=d.get(curr, [])
                    for dest_used in l:
                        dest, used = dest_used
                        if used: continue
                        path.append(dest)
                        dest_used[1]=True
                        rec()
                        path.pop()
                        dest_used[1]=False
            try:
                rec()
                print("false")
                assert(False)
            except:
                pass
            return path
    

Log in to reply
 

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