Alien Dictionary

Intuition

Solution

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        digraph = DiGraph(26)

        for i in range(len(words) - 1):
            index = 0
            w1, w2 = words[i], words[i + 1]
            while index < len(w1) and index < len(w2):
                if w1[index] != w2[index]:
                    digraph.add_edge(
                        ord(w2[index]) - ord('a'),
                        ord(w1[index]) - ord('a')
                    )
                    break
                index += 1

        order = DFSOrder(digraph)
        if order.cycle:
            return ""
        used = set()
        for w in words:
            for c in w:
                used.add(ord(c) - ord('a'))
        return ''.join([chr(i + ord('a')) for i in order.postorder if i in used])