269. Alien Dictionary

alien_dict.py

from collections import defaultdict

class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        graph = defaultdict(list)        
                
        # build graph
        for w1, w2 in zip(words, words[1:]):
            for a, b in zip(w1, w2):
                # add first diff char
                # exclude single char 
                if a != b: 
                    graph[a].append(b)
                    break
        
        # toposort graph
        visited = set()
        stack = []
        
        def topo_dfs(node, path):
            if node in visited:
                return
            visited.add(node)
            
            path.add(node)
            for nei in graph[node]:
                if nei in path or topo_dfs(nei, path):
                    return True
            stack.insert(0, node)
            path.remove(node)
        
        chars = set()
        for w in words:
            for c in w:
                chars.add(c)
        
        for c in chars:
            if topo_dfs(c, set()):
                return ''
        
        return ''.join(stack)