Simple Python topo-sort solution


  • 0
    S

    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]:
                    graph[v[i]].append(w[i])
                    break
        
        # 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
        marked.add(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited and self.dfs_has_cycle(graph, neighbor, visited, marked, order):
                return True
        marked.remove(node)
        visited.add(node)
        order.append(node)

Log in to reply
 

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