Python stack overflow


  • 0

    The last test case is too big for a recursive solution to get accepted.

    import collections
    class Solution(object):
        def sequenceReconstruction(self, org, seqs):
            """
            :type org: List[int]
            :type seqs: List[List[int]]
            :rtype: bool
            """
            n = len(org)
            graph = collections.defaultdict(set)
            visited = {}
            incomings = collections.defaultdict(int)
            nodes = set()
            for seq in seqs:
                if len(seq) == 1:
                    nodes |= {seq[0]}
                for i in range(0, len(seq) - 1):
                    start, end = seq[i], seq[i+1]
                    graph[start].add(end)
                    nodes |= {start, end}
    
            order = []
            visited = collections.defaultdict(int)
            def dfs(root, graph, order, visited, incomings):
                visited[root] = 1
                nbrs = graph.get(root, [])
                for nbr in graph.get(root, []):
                    visit = visited.get(nbr, 0)
                    if visit == 0:
                        incomings[nbr] += 1
                        if not dfs(nbr, graph, order, visited, incomings):
                            return False
                    elif visit == 1:
                        return False
                    elif visit == 2:
                        incomings[nbr] += 1
                order.append(root)
                visited[root] = 2
                return True
                
            for node in nodes:
                if visited[node] == 0:
                    if not dfs(node, graph, order, visited, incomings):
                        return False
            count = 0
            for node in incomings:
                if incomings[node] == 0:
                    count += 1
                    if count == 2:
                        return False
            if order[::-1] == org:
                return True
            return False
    

Log in to reply
 

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