Python 35ms solution using DFS + topological sort with in-code explaination

  • 0
    The idea is to contruct a directed graph from all possible orderings of input characters,
    then get the topological order if it's a DAG. Return '' if there is a cycle.
    If any character's topological order cannot be determined, simply append it to the result.
    Example case:
        ["zyx", "zx"] 
    where 'z' is not in the DAG, we should add it to the topological order ['y','x']
    from collections import defaultdict
    NEVER, ONPATH, DONE = 0, 1, 2 # visiting status for DFS
    class Solution(object):
        def alienOrder(self, words):
            :type words: List[str]
            :rtype: str
            # get all possible edges to construct DAG
            adj = defaultdict(set)
            char_set = set(words[-1])
            for i in range(len(words)-1):
                for c1, c2 in zip(words[i], words[i+1]):
                    if c1 != c2:
            # try to get the topological order of the DAG
            # also pass the overall character set to add to result if necessary
            return self.topo_sort(adj, char_set)
        def topo_sort(self, adj, cset):
            visit = defaultdict(int)
            tp_order = []
            for u in adj.keys():
                if not visit[u] and self.hasCycle(adj, u, visit, tp_order, cset):
                    return ''
            return ''.join(tp_order[::-1] + list(cset))
        def hasCycle(self, adj, u, visit, tp_order, cset):
            if visit[u] == DONE:
                return False
            visit[u] = ONPATH
            for v in adj[u]:
                if visit[v] == ONPATH or self.hasCycle(adj, v, visit, tp_order, cset):
                    return True
            visit[u] = DONE
            return False

    0_1494346548346_Screen Shot 2017-05-10 at 12.11.50 AM.png

Log in to reply

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