Alien Dictionary

题目

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:
Given the following words in dictionary,

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

The correct order is:"wertf".

Example 2:
Given the following words in dictionary,

[
  "z",
  "x"
]

The correct order is:"zx".

Example 3:
Given the following words in dictionary,

[
  "z",
  "x",
  "z"
]

The order is invalid, so return"".

Note:

1. You may assume all letters are in lowercase.
2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
3. If the order is invalid, return an empty string.
4. There may be multiple valid order of letters, return any one of them is fine.

思路分析

这道题可以用topological sort来实现，但是怎么来build一个graph呢？创建一个graph是本题的难点，怎么样才能创建好graph呢？要根据lexicographically的特点来构图

举例来讲：

通过"wrt"和"wrf"，我们可以得到t在f的前面

通过"ett"和"rftt"，我们可以得到e在r的前面

本题的另外一个容易出错的地方就是我们一般把graph的value设置成一个set，这样我们就有distict的neighbor，但是在这道题中我们用set就会出现一种错误，比如["za","zb","ca","cb"]，a-b线出现了两次，那么b的indegree变成了2，但是key a的value中只有一个b（因为是set），也就是说会出现b本来只是a的一个neighbor，但是b的indegree却是2，这就是错误之处。有两种方式来避免这个错误：

方法1是在将cur的indegree加1之前先判断它是不是已经在pre的neighbor中了，如果已经在pre的neighbor中了，就不需要再加1了

方法2是用list，而不是用set来存储每一个vertex的neighbor，这样做的好处是neighbor的个数与每一个neighbor的indegree是一致的，因为list是允许重复出现的。这样做的缺点就是额外增加了存储和运算时间

用set来存储graph中每一个vertex的neighbor

class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        chars = set("".join(words))
        graph = {char: set() for char in chars}
        indegree = {char: 0 for char in chars}
        for word1, word2 in zip(words, words[1:]):
            for pre, cur in zip(*(word1, word2)):
                if pre != cur: 
                    if (pre not in graph) or (pre in graph and cur not in graph[pre]) :   <<<<<
                        graph[pre].add(cur)
                        indegree[cur] += 1
                    break
        queue = [char for char in indegree if indegree[char] == 0]
        result = ""
        while queue:
            char = queue.pop()
            result += char
            for neighbor in graph[char]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0: queue.append(neighbor)
        if len(result) == len(chars): return result
        return ""

用list来存储graph中每一个vertex的neighbor

class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        chars = set("".join(words))
        graph = {char: [] for char in chars}
        indegree = {char: 0 for char in chars}
        for word1, word2 in zip(words, words[1:]):
            for pre, cur in zip(*(word1, word2)):
                if pre != cur: 
                    graph[pre].append(cur)
                    indegree[cur] += 1
                    break
        queue = [char for char in indegree if indegree[char] == 0]
        result = ""
        while queue:
            char = queue.pop()
            result += char
            for neighbor in graph[char]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0: queue.append(neighbor)
        if len(result) == len(chars): return result
        return ""