# Topological Sort using python

• ``````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 = []``````

• 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.

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

• 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``````

• 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.

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

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