Alien Dictionary giving wrong answer. Help


  • 0
    D

    Hi,
    I am trying to write the code for alien dictionary in python. But it's giving me wrong result. I tried to find the fault but couldn't. Hence, the help. Can someone please tell me where I am going wrong.

    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

Log in to reply
 

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