My AC not-so-pythonic solution


  • 0
    R

    This is just a translation of my java code into python for the question. It runs in around 160 ms.

    def canFinish(self, numCourses, prerequisites): 
            def isValid(li,num,mp,clist): # function to perform dfs on a given course
                valid = True
                if num in mp:
                    assoc = mp[num]
                    for i in assoc:
                        if i in clist:
                            return False
                        elif i not in li:
                            clist.append(num)
                            valid = valid and isValid(li,i,mp,clist)
                            if not valid:
                                return False
                            clist.pop()
                li.append(num)
                return True
                
            le = len(prerequisites)
            if numCourses==0 or le==0:
                return True
            mp = {}
            valid = True
            for item in prerequisites: # Create a dictionary to map between a course and a list of its dependencies
                if item[1] in mp:
                    mp[item[1]].append(item[0])
                else:
                    mp[item[1]] = [item[0]]
            li = []
            clist = []
            for i in range(numCourses): # For each course do a dfs to find if there is a cycle in its dependents
                valid = valid and isValid(li,i,mp,clist)
            return valid

Log in to reply
 

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