share my python codes


  • 0
    C

    This is topological sort?

    class Solution(object):
        def findItineraryDFS(self, tickets):
            """
            :type tickets: List[List[str]]
            :rtype: List[str]
            """
            graph, path = {}, []
            for ticket in tickets:
                graph[ticket[0]] = graph.get(ticket[0], []) + [ticket[1]]
                
            for key in graph.keys():
                graph[key].sort(reverse=True)
                
            def DFS(s):
                stack = graph.get(s, [])
                while stack:
                    DFS(stack.pop())
                path.append(s)
                
            DFS('JFK')
            return path[::-1]
            
            
        def findItinerary(self, tickets):
            """
            :type tickets: List[List[str]]
            :rtype: List[str]
            """
            graph, path = {}, []
            for ticket in tickets:
                graph[ticket[0]] = graph.get(ticket[0], []) + [ticket[1]]
                
            for key in graph.keys():
                graph[key].sort()
                
            def DFS(s):
                q = graph.get(s, [])
                while q:
                    DFS(q.pop(0)) 
                path.append(s)
                
            DFS('JFK')
            return path[::-1]
    

    Refer:
    (1) http://www.programcreek.com/2015/03/leetcode-reconstruct-itinerary-java/
    (2)http://bookshadow.com/weblog/2016/02/05/leetcode-reconstruct-itinerary/


Log in to reply
 

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