Leetcode 269 Solution

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        nodes = {ch for word in words for ch in word}
        parents = collections.defaultdict(set)
        children = collections.defaultdict(set)

        for i in range(1, len(words)):
            word1 = words[i - 1]
            word2 = words[i]

            minlen = min(len(word1), len(word2))

            j = 0
            while j < minlen:
                if word1[j] != word2[j]:
                    children[word1[j]].add(word2[j])
                    parents[word2[j]].add(word1[j])
                    break
                j += 1

            if j == minlen and len(word1) > len(word2):
                return ""

        q = collections.deque()
        for node in nodes:
            if len(parents.get(node, {})) == 0:
                q.append(node)

        ans = []
        while len(ans) < len(nodes):
            if not q:
                return ""

            node = q.popleft()
            ans.append(node)

            child_nodes = children.get(node, set())
            for child_node in child_nodes:
                parents[child_node].remove(node)

                if len(parents[child_node]) == 0:
                    q.append(child_node)

        return "".join(ans)