Topological Sort using python


  • 0
    S
    class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        all_words = "".join(words)
        chars = set(all_words)
        letters={}
        for character in chars:
            letters[character]=self.Node(character)
        for f, b in zip(words[:-1], words[1:]):
            for i in range (0, min(len(f),len(b))):
                if(f[i] != b[i]):
                    letters[f[i]].next.append(letters[b[i]])
                    break
        res=[]
        for letter in letters:
            if(self.isCyclic(letters[letter], res)):
                return ""
        res.reverse()
        ans =""
        for each in res:
          ans = ans+str(each)
        return ans
    
    def isCyclic(self, node, res):
        if(node.tested):return False
        if(node.visited):return True
        node.visited = True
        for child in node.next:
            if(self.isCyclic(child, res)):
                return True
        node.tested = True
        res.append(node.val)
        return False
        
    class Node:
        def __init__(self,val):
            self.val = val
            self.tested = False
            self.visited = False
            self.next = []

  • 0
    D

    Do you really want to do res = res.append(node.val). Because append method return None. Hence res becomes None. Can you tell me why you are doing that. That makes me think whether this code works or not.


  • 0
    S

    I'm sorry I made a typo there. It's strange leetcode accepted my code. Thanks!


  • 0
    D

    That's great to know. However, my code isn't working. I tried to do what you did. But it gives wrong. answer. Can you please let me know. I have an interview soon. Hence, asking your help

    class Solution(object):
        
        class GraphNode (object):
            
            def __init__(self,val):
                self.value =  val
                self.linkedTo =[]
                self.isVisited=False
                self.tested=False
        
        def alienOrder(self, words):
            """
            :type words: List[str]
            :rtype: str
            """
            return self.alienOrdeHelper(words)
        def alienOrdeHelper(self, words):
            # Initially, you thought was the you can take a word at a time and create a graph.
            # However, if you observer closely then you will come to know that the relationship between characters
            # is not within a word, but among each others. The question says word"s" are sorted lexicographically. 
            # The characters within the words aren't sorted. Hence, you need to use pair of words to create a graph.  
            # Hence, you see that we compare pairs. 
            dictUniqChar = {}
            for uniqChar  in set(''.join(words)):
                dictUniqChar[uniqChar] = self.GraphNode(uniqChar)
            
            for word1, word2 in zip(words[:-1], words[1:]):
                # Since you are using 2 words, if one exhaust then it doesn't matter 
                # what characters are left with others words isn't of much help.
                # Hence, the min function. 
                for i in range(min(len(word1), len(word2))):
                    if word1[i] != word2[i]:
                        dictUniqChar[word1[i]].linkedTo.append(dictUniqChar[word2[i]])
                        # This is a heuristic, if any 2 chars don't match. Then we can't say anything about the other 
                        # i believe that's the reason. 
                        break
                res=[]
                for node in dictUniqChar.values():
    #                 print node.value
                    if self.hasCycle(node, res):
                        print node.value
                        return ''
                res.reverse()
                retStr = ''
                for eachChar in res:
                    retStr += eachChar
                
                return retStr
                    
        def hasCycle(self, vertex, postorderdag):
            # tested is an heuristic, as per understanding. 
            # to stop the flow. 
            if vertex.tested:
                return False
            
            if vertex.isVisited:
                return True
            vertex.isVisited = True
            
            for adjV in vertex.linkedTo:
                if self.hasCycle(adjV, postorderdag):
                    return True
            vertex.tested = True
            postorderdag.append(vertex.value)
            return False

  • 0
    S

    Hi,I hope it's not too late :D
    The error is that all your code after "break" in function "alienOrdeHelper" are still in the scope of that "zip" forloop. They should be outside that forloop.


  • 0
    D

    Thanks shihan. It's never too late. Thanks a tonn for helping my find my bug. I was going crazy over this. Thanks. :)


Log in to reply
 

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