Alien Dictionary

DFS

First, build the graph, here in this situation, the graph is a 2D array graph, where graph[i][j] == true means char i precedes char j.
Iterate through the list of word, and compare word1 and word2, if char i in word1 != char i in word2, which means char j precedes char j.

Start to do DFS,
visited[i] = -1. Not even exist
visited[i] = 0. Exist, not visited yet
visited[i] = 1. visiting
visited[i] = 2. visited

while doing the DFS, put the visited char in the stack. This stack stores the order of each char.

from collections import defaultdict
from collections import deque, Counter
class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """


        queue = deque()
        visited = 26 * [-1]
        graph = [[False for i in range(26)] for j in range(26)]

        # build graph
        for i in range(len(words)):
            for w in words[i]:
                visited[ord(w)-ord('a')] = 0

            if i > 0:
                w1 = words[i-1]
                w2 = words[i]
                length = min(len(w1), len(w2))

                for j in range(length):
                    if w1[j] != w2[j]:
                        graph[ord(w1[j])-ord('a')][ord(w2[j])-ord('a')] = True
                        break


        def dfs(i, visited, graph, queue):
            visited[i] = 1  # visiting
            for j in range(26):
                if graph[i][j]:
                    if visited[j] == 1: # visited, indicates there is a cycle
                        return False
                    if visited[j] == 0: # not visited yet. call DFS
                        if not dfs(j, visited, graph, queue):
                            return False
            visited[i] = 2 # visited
            queue.append(chr(i+97))
            return True


        for i in range(26):
            if visited[i] == 0:
                if not dfs(i, visited, graph, queue):
                    return ""

        res = ""
        while queue:
            res += queue.pop()

        return res