269. Alien Dictionary

• Ensure each word has a entry set, even if it is empty
• visited list has two values, False been the node has already been visited, True been the node is in the current path
• if second word is subset of first, but is shorter, it is invalid

class Solution(object):
    def alienOrder(self, words):
        adj = { c:set() for w in words for c in w}

        prev = words[0]

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

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

            if len(word2) < len(word1) and word2[:length] == word1[:length]:
                return ""


            for j in range(length):
                if word1[j] != word2[j]:
                    adj[word1[j]].add(word2[j])
                    break

            prev = word2

        res = []
        visited = {}

        def dfs(src):
            if src in visited:
                return visited[src]

            visited[src] = True # inpath

            for node in adj[src]:
                if dfs(node):
                    return True
            
            visited[src] = False #visited
            res.append(src)

        for c in adj:
            if dfs(c): # if True, has loop
                return ""

        return "".join(reversed(res))