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


  • 0
    X
    """
    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):
                char_set.update(words[i])
                for c1, c2 in zip(words[i], words[i+1]):
                    if c1 != c2:
                        adj[c1].add(c2)
                        break
            # 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
            
            tp_order.append(u)
            cset.remove(u)
            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.