Python Solution Using Kahn's Algorithm


  • 0
    M
        def alienOrder(self, words):
            """
            :type words: List[str]
            :rtype: str
            """
            from collections import deque, defaultdict
                    
            letters = set(''.join(words))
            D = { letter: set() for letter in letters }
            
            for i in xrange(len(words)-1):
                for a, b in zip(words[i], words[i+1]):
                    if a != b:
                        D[a].add(b)
                        break
            
            in_edges = defaultdict(int)
            for letter in D:
                for dep in D[letter]:
                    in_edges[dep] += 1
            
            Q, L = deque([letter for letter in letters if in_edges[letter] == 0]), ''
            
            while Q:
                letter = Q.popleft()
                L += letter
                for dep in D[letter]:
                    in_edges[dep] -= 1
                    if in_edges[dep] == 0:
                        Q.appendleft(dep)
            
            return L if len(L) == len(letters) else ''
    

Log in to reply
 

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