def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        graph, res, allchars  = {}, '', set(''.join(words))
        for i in allchars:
            graph[i] = Node()

        for i in xrange(len(words)-1):
            for j in zip(words[i], words[i+1]):
                if j[0] != j[1]:
                    graph[j[0]].children.add(j[1])
                    graph[j[1]].parent.add(j[0])
                    break
        while allchars:
            cur = set(i for i in allchars if graph[i].children and not graph[i].parent)
            if not cur:
                return res + ''.join(allchars) if not [k for k in allchars if graph[k].parent] else ''
            res += ''.join(cur)
            allchars -= cur
            # print (allchars, cur)
            for j in allchars: # ca it be graph?
                graph[j].parent -= cur

New method with parents and children

Time Complexity: O(V + E). Space: O(V). V最大26. Edge最大为words.length.

class Solution(object):
    def alienOrder(self, words):
        allchars = set(''.join(words))
        parents, children = collections.defaultdict(set), collections.defaultdict(set)
        for i in xrange(1, len(words)):
            for c1, c2 in zip(words[i], words[i-1]):
                if c1 != c2:
                    children[c2].add(c1)
                    parents[c1].add(c2)
                    break
        res = []
        while allchars:
            cur = set([char for char in allchars if char in children and not parents[char]])
            if not cur:
                for char in allchars:
                    if parents[char]:
                        return ''
                    res.append(char)
                return ''.join(res)
            allchars -= cur
            res.extend(cur)
            for char in allchars:
                parents[char] -= cur
        return ''.join(res)