Solve both recursively and iteratively in Python


  • 1
    A
    class Solution(object):
        def findItinerary(self, tickets):
            """
            :type tickets: List[List[str]]
            :rtype: List[str]
            """
            graph = self.buildGraph(tickets)
            path = []
            path.append("JFK")
            self.dfs(graph, path, tickets)
            return path
     
        def dfs(self, graph, path, tickets):
            to = graph[path[-1]]
            to.sort()
            for i in range(len(to)):
                d = to.pop(i)
                path.append(d)
                self.dfs(graph, path, tickets)
                if len(path) == len(tickets) + 1:
                    return
                path.pop()
                to.insert(i,d)
            return
        
        def buildGraph(self, tickets):
            graph = dict()
            for ticket in tickets:
                if ticket[0] in graph:
                    graph[ticket[0]].append(ticket[1])
                else:
                    graph[ticket[0]] = [ticket[1]]
                if ticket[1] not in graph:
                    graph[ticket[1]] = []
            return graph
     
    
    
    class Solution(object):
        def findItinerary(self, tickets):
            """
            :type tickets: List[List[str]]
            :rtype: List[str]
            """
            graph = self.buildGraph(tickets)
            path = []
            path.append("JFK")
            self.dfs(graph, path, tickets)
            return path
            
            
        def dfs(self, graph, path, tickets):
            dq = graph[path[-1]]
            count = len(dq)
            while count > 0:
                count -= 1
                path.append(dq.popleft())
                self.dfs(graph, path, tickets)
                if len(path) == len(tickets) + 1:
                    return
                dq.append(path.pop())
            return
            
        def buildGraph(self, tickets):
            graph = dict()
            for ticket in tickets:
                if ticket[0] in graph:
                    graph[ticket[0]].append(ticket[1])
                else:
                    graph[ticket[0]] = [ticket[1]]
                if ticket[1] not in graph:
                    graph[ticket[1]] = []
            for d in graph:
                temp = graph[d]
                temp.sort()
                graph[d] = collections.deque(temp)
            return graph
        
    
    
    class Solution(object):
        def findItinerary(self, tickets):
            """
            :type tickets: List[List[str]]
            :rtype: List[str]
            """
            graph = self.buildDigraph(tickets)
            result = []
            stack = ["JFK"]
            while len(stack) != 0:
                u = stack[-1]
                adj = graph[u]
                adj.sort()
                adj.reverse()
                if len(adj) == 0:
                    result.append(stack.pop())
                else:
                    stack.append(adj.pop())
            result.reverse()
            return result
         
        def buildDigraph(self, arcs):
            graph = {}
            for arc in arcs:
                if arc[0] in graph:
                    graph[arc[0]].append(arc[1])
                else:
                    graph[arc[0]] = [arc[1]]
                if arc[1] not in graph:
                    graph[arc[1]] = []
            return graph

Log in to reply
 

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