269. Alien Dictionary

https://leetcode.com/problems/alien-dictionary/leetcode.com

字典是以 lexicographically 排列的，那单个字母间的排序信息只能通过单词 one by one 的比较来获得，遍历比较后，可以知道字母之间 one to one 的前后关系。

把这种前后关系当作 node 之间的 bridge 来理解的话，就可以把所有字母理解为一个graph，那么想得到 overall 的字母顺序，对这个 graph 进行topological sort就可以。

topological sort 可以用 indegree Sort 或者 DFS 来做。

什么是拓扑排序（Topological Sorting）简书

Topological Sorting using Depth First Search (DFS)OpenGenus IQ: Computing Expertise & Legacy

DFS

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        edges = self.graphify(words)
        return self.topologicalSort(edges)
    
    
    def graphify(self, words):
        edges = {letter: set() for letter in words[0]}
        for i in range(1, len(words)):
            prev, curr = words[i-1], words[i]
            #print("search words: %s | %s" % (prev, curr))
            edge_found = False
            # 无效情况 e.g. ["abcd", "ab"]
            if prev.startswith(curr) and len(prev) > len(curr):
                return {}
            for j in range(len(curr)):
                # 发现新字母
                if curr[j] not in edges:
                    edges[curr[j]] = set()
                # 发现 edge
                if not edge_found and j < len(prev) and curr[j] != prev[j]:
                    # 如果是新 edge，就记录
                    if (curr[j] not in edges[prev[j]]):
                        #print("edge found: %s -> %s" % (prev[j], curr[j]))
                        edges[prev[j]].add(curr[j])
                    # 不管是新 edge 还是已经记录过的 edge，后面的字母相对顺序都没有意义了。
                    edge_found = True
        return edges
    
    
    def topologicalSort(self, edges):
        order, path, visited = [], [], []
        for w in edges:
            if self.dfs(w, edges, path, visited, order):
                return ""
        return "".join(reversed(order))
    
    
    def dfs(self, node, edges, path, visited, order):
        if node in path:  return True
        if node in visited:  return
        path.append(node)
        for child in edges[node]:
            if self.dfs(child, edges, path, visited, order):
                return True
        path.pop()
        visited.append(node)
        order.append(node)
        return False
        

Indegree Sort

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        edges, indegree = self.graphify(words)
        return self.indgreeSort(edges, indegree)
    
    
    def graphify(self, words):
        edges = {letter: set() for letter in words[0]}
        indegrees = {letter: 0 for letter in words[0]}
        for i in range(1, len(words)):
            prev, curr = words[i-1], words[i]
            #print("search words: %s | %s" % (prev, curr))
            edge_found = False
            if prev.startswith(curr) and len(prev) > len(curr):
                return {}, {}
            for j in range(len(curr)):
                if curr[j] not in edges:
                    edges[curr[j]] = set()
                    indegrees[curr[j]] = 0
                if not edge_found and j < len(prev) and curr[j] != prev[j]:
                    if (curr[j] not in edges[prev[j]]):
                        #print("edge found: %s -> %s" % (prev[j], curr[j]))
                        edges[prev[j]].add(curr[j])
                        indegrees[curr[j]] += 1
                    edge_found = True
        return edges, indegrees
    
    
    def indgreeSort(self, edges, indegrees):
        order = []
        q = collections.deque([k for (k, v) in indegrees.items() if v == 0])
        while q:
            node = q.popleft()
            for child in edges[node]:
                indegrees[child] -= 1
                if indegrees[child] == 0:
                    q.append(child)
            order.append(node)
        return "".join(order) if len(order) == len(indegrees) else ""