Python beat 96%. With idea description and comments


  • 0
    X

    See comment for ideas.

    class Solution(object):
        
        """
            This problem is about build tree + DFS. 
            When DFS, check for circle (any children are already on the PATH)
            
            build tree: according to prerequisites, build a tree (actually graph) where a -> b mean a is prerequisite for b. (here I use parentChildren to record tree structure. You can also use you own class to do this)
            
            Then start from each node (i.e. course) and do DFS. When the child is on the path, circle detected -> not good, return False
        """
        def DFS(self, root, onPath, parentChildren, explored):
            if not parentChildren.has_key(root):
                # it means root does not have any children (i.e., it is not prerequisite of any classes)
                del onPath[root]
                return True
            
            for i in range(len(parentChildren[root])):
                child = parentChildren[root][i]
                
                # circle detected
                if onPath.has_key(child): return False
                
                # if we have explored this course, do nothing
                if explored.has_key(child): 
                    continue
                
                onPath[child] = 1
                explored[child] = 1
                
                if self.DFS(child, onPath, parentChildren, explored) == False:
                    return False
            del onPath[root]
            return True
            
            
        def canFinish(self, numCourses, prerequisites):
            """
            :type numCourses: int
            :type prerequisites: List[List[int]]
            :rtype: bool
            """
            coursesPool = []
            parentChildren = {}
            
            # parentChildren will record the graph structure.
            for pair in prerequisites:
                if parentChildren.has_key(pair[0]):
                    parentChildren[pair[0]].append(pair[1])
                else:
                    parentChildren[pair[0]] = [pair[1]]
            
            parentChildren[-1] = [key for key in range(numCourses)]
            #print parentChildren
            onPath = {-1:1}
            explored = {}
            return self.DFS(-1, onPath, parentChildren, explored)
                    
    

Log in to reply
 

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