Backtracking or depth first search


  • 0
    S
    class Solution(object):
        def findItinerary(self, tickets):
            """
            :type tickets: List[List[str]]
            :rtype: List[str]
            """
    
            def backtrack(state, graph, k, result):
                if len(state) == k:
                    for x in state:
                        result.append(x)
                    self.done = True
                else:
                    for nxt in graph[state[-1]]:
                        if self.done == False:
                            graph[state[-1]].remove(nxt)
                            state.append(nxt)
                            backtrack(state, graph, k, result)
                            state.pop()
                            graph[state[-1]].insert(bisect.bisect_left(graph[state[-1]], nxt), nxt)
    
            table = collections.defaultdict(list)
            for ticket in tickets:
                fro = ticket[0]
                to = ticket[1]
                table[fro].insert(bisect.bisect_left(table[fro], to), to)
    
            self.done = False
            state = ["JFK"]
            k = len(tickets) + 1
            result = []
            backtrack(state, table, k, result)
            return result

Log in to reply
 

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