Clear Python DFS


  • 1

    A variant of DFS.
    When traversing, move the smallest neighbour that you are going to visit to the worst position in its neighbour list.

    class Solution(object):
        def findItinerary(self, tickets):
            """
            :type tickets: List[List[str]]
            :rtype: List[str]
            """
            from collections import deque
            graph = {}
            for ticket in tickets:
                graph[ticket[0]] = graph.get(ticket[0], []) + [ticket[1]]
            for start in graph:
                graph[start] = deque(sorted(graph[start]))
                
            def dfs(root, graph, path, maxLen):
                if len(path) == maxLen:
                    return True
                for k in xrange(len(graph.get(root, []))):
                    end = graph[root].popleft()
                    path.append(end)
                    if dfs(end, graph, path, maxLen):
                        return True
                    path.pop()
                    graph[root].append(end)
    
            path = ["JFK"]
            dfs("JFK", graph, path, len(tickets) + 1)
            return path
    

Log in to reply
 

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