# Simple to understand Python solution

• from collections import defaultdict
class Solution(object):
def alienOrder(self, words):
g = {}
self.makeGraph(g, words)
return "".join(self.toposort(g))

def makeGraph(self, g, words):
self.createVertices(g, words)
for i in xrange(len(words)-1):
self.insertOrder(g, words[i], words[i+1])

def createVertices(self, g, words):
uniqueChars = set(''.join(words))
for c in uniqueChars: g[c] = []

def insertOrder(self, g, s1, s2):
p1 = p2 = 0
while p1 < len(s1) and p2 < len(s2):
if s1[p1] != s2[p2]:
if s2[p2] not in g[s1[p1]]:
g[s1[p1]].append(s2[p2])
return
p1 += 1
p2 += 1

def toposort(self, g):
stack = []
visited = defaultdict(lambda: None)
alive = defaultdict(lambda: None)
for v in g:
# cycle detected, return empty array
if not visited[v] and self.toposort_(g, v, visited, stack, alive):
return []
return reversed(stack)

# if detected cycle, return True, otherwise False
def toposort_(self, g, v, visited, stack, alive):
visited[v] = True
alive[v] = True
for n in g[v]:
if not visited[n] and self.toposort_(g, n, visited, stack, alive):
return True
elif visited[n] and alive[n]:
return True
alive[v] = False
stack.append(v)
return False

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