# Time:  O(|V|+|E|) = O(26 + 26^2) = O(1)
# Space: O(|V|+|E|) = O(26 + 26^2) = O(1)

class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        # Find ancestors of each node by DFS.
        nodes, ancestors = sets.Set(), {}
        for i in xrange(len(words)):
            for c in words[i]:
                nodes.add(c)
        for node in nodes:
            ancestors[node] = []
        for i in xrange(1, len(words)):
            self.findEdges(words[i - 1], words[i], ancestors)

        # Output topological order by DFS.
        result = []
        visited = {}
        for node in nodes:
            if self.topSortDFS(node, node, ancestors, visited, result):
                return ""
        
        return "".join(result)


    # Construct the graph.
    def findEdges(self, word1, word2, ancestors):
        min_len = min(len(word1), len(word2))
        for i in xrange(min_len):
            if word1[i] != word2[i]:
                ancestors[word2[i]].append(word1[i])
                break


    # Topological sort, return whether there is a cycle.
    def topSortDFS(self, root, node, ancestors, visited, result):
        if node not in visited:
            visited[node] = root
            for ancestor in ancestors[node]:
                if self.topSortDFS(root, ancestor, ancestors, visited, result):
                    return True
            result.append(node)
        elif visited[node] == root:
            # Visited from the same root in the DFS path.
            # So it is cyclic.
            return True
        return False

@@ -82,22 +82,1762 @@
 1)%0A%0A
-class Solution
+# BFS solution.%0Aclass Solution(object):%0A    def alienOrder(self, words):%0A        %22%22%22%0A        :type words: List%5Bstr%5D%0A        :rtype: str%0A        %22%22%22%0A        # Find ancestors of each node by BFS%0A        result, zero_in_degree_queue, in_degree, out_degree = %5B%5D, %5B%5D, %7B%7D, %7B%7D%0A        nodes = sets.Set()%0A        for i in xrange(len(words)):%0A            for c in words%5Bi%5D:%0A                nodes.add(c)%0A        %0A        for i in xrange(1, len(words)):%0A            self.findEdges(words%5Bi - 1%5D, words%5Bi%5D, in_degree, out_degree)%0A        %0A        for node in nodes:%0A            if node not in in_degree:%0A                zero_in_degree_queue.append(node)%0A        %0A        while zero_in_degree_queue:%0A            precedence = zero_in_degree_queue.pop()%0A            result.append(precedence)%0A            %0A            if precedence in out_degree:%0A                for course in out_degree%5Bprecedence%5D:%0A                    in_degree%5Bcourse%5D.discard(precedence)%0A                    if not in_degree%5Bcourse%5D:%0A                        zero_in_degree_queue.append(course)%0A            %0A                del out_degree%5Bprecedence%5D%0A        %0A        if out_degree:%0A            return %22%22%0A%0A        return %22%22.join(result)%0A%0A%0A    # Construct the graph.%0A    def findEdges(self, word1, word2, in_degree, out_degree):%0A        str_len = min(len(word1), len(word2))%0A        for i in xrange(str_len):%0A            if word1%5Bi%5D != word2%5Bi%5D:%0A                if word2%5Bi%5D not in in_degree:%0A                    in_degree%5Bword2%5Bi%5D%5D = sets.Set()%0A                if word1%5Bi%5D not in out_degree:%0A                    out_degree%5Bword1%5Bi%5D%5D = sets.Set()%0A                in_degree%5Bword2%5Bi%5D%5D.add(word1%5Bi%5D)%0A                out_degree%5Bword1%5Bi%5D%5D.add(word2%5Bi%5D)%0A                break%0A%0A%0A# DFS solution.%0Aclass Solution2
 (obj

Update alien-dictionary.py