Create alien-dictionary.py

kamyu104 · kamyu104 · commit 85d2095a699d · 2015-08-25T22:20:39.000+08:00
diff --git a/Python/alien-dictionary.py b/Python/alien-dictionary.py
@@ -0,0 +1,53 @@
+# Time:  O(|V|+|E|) = O(26 + 26^2) = O(1)
+# Space: O(|E|) = O(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 = {}, {}
+        for i in xrange(len(words)):
+            for c in words[i]:
+                nodes[c] = True
+
+        for node in nodes.keys():
+            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.keys():
+            if self.topSortDFS(node, node, ancestors, visited, result):
+                return ""
+        
+        return "".join(result)
+
+
+    # Construct the graph.
+    def findEdges(self, word1, word2, ancestors):
+        str_len = min(len(word1), len(word2))
+        for i in xrange(str_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
