Python Solution Using Kahn's Algorithm

  • 0
        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:
            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:
            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.