Simple Python topo-sort solution

  • 0

    Only two steps, first grab the letters order to build graph, then apply topo-sort.

    class Solution(object):
    def alienOrder(self, words):
        :type words: List[str]
        :rtype: str
        if not words:
            return ''
        if len(words) == 1:
            return words[0]
        # build graph
        graph = {node: [] for node in set(''.join(words))}
        for v, w in zip(words[:-1], words[1:]):
            for i in xrange(min(len(v), len(w))):
                if v[i] != w[i]:
        # apply topo sort
        return self.topo_sort(graph)
    def topo_sort(self, graph):
        order = []
        visited = set()
        marked = set()
        for node in graph:
            if node not in visited and self.dfs_has_cycle(graph, node, visited, marked, order):
                return ''
        return ''.join(order[::-1])
    def dfs_has_cycle(self, graph, node, visited, marked, order):
        if node in marked:
            return True
        for neighbor in graph[node]:
            if neighbor not in visited and self.dfs_has_cycle(graph, neighbor, visited, marked, order):
                return True

Log in to reply

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