Simple to understand Python solution

  • 0
    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]]:
                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
            return False

Log in to reply

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