# 269. Alien Dictionary

{% embed url="<https://leetcode.com/problems/alien-dictionary/>" %}

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

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

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

{% embed url="<https://www.jianshu.com/p/b59db381561a>" %}

{% embed url="<https://iq.opengenus.org/topological-sorting-dfs/>" %}

{% tabs %}
{% tab title="DFS" %}

```python
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
        
```

{% endtab %}

{% tab title="Indegree Sort" %}

```python
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 ""
```

{% endtab %}
{% endtabs %}
