​LeetCode刷题实战269：火星词典

示例 1：
输入:
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]
输出: "wertf"

示例 2：
输入:
[
  "z",
  "x"
]
输出: "zx"

示例 3：
输入:
[
  "z",
  "x",
  "z"
] 
输出: "" 
解释: 此顺序是非法的，因此返回 ""。

class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        # 1.构建图
        hashMap = {}
        for i in range(len(words)-1):
            for j in range(min(len(words[i]), len(words[i+1]))):
                # 如果字符相同，比较下一个
                if words[i][j] == words[i+1][j]:
                    continue
                # 保存第一个不同的字符顺序，位于前面的字母作为key，位于后面的字母存到set中作为值
                else:
                    s=hashMap.get(words[i][j],set())
                    s.add(words[i+1][j])
                    hashMap[words[i][j]] = s
                    break
        degrees = [-1 for _ in range(26)]
        # 将出现过的字符的出度设定为0，为了统计所有出现的不同的字母的个数
        # 没有出现的字母出度为-1，出现了的字母的出度为非负数
        for word in words:
            for c in word:
                degrees[ord(c)-ord("a")] = 0
        for key,value in hashMap.items():
            for val in value:
                # 出现了的字母的入度+1
                degrees[ord(val)-ord("a")] += 1
        # 创建一个Queue保存入度为0的节点
        Q = []
        total = 0
        for i in range(26):
            if degrees[i] != -1:
                total+=1
            if degrees[i] == 0:
                Q.append(chr(i+ord("a")))
        res = ""
        while Q:
            t = Q.pop(0)
            res+=t
            # 图中的最后一个字母，在本例中例如f是不在hashmap中的
            if t in hashMap:
                for c in hashMap[t]:
                    # 将邻接点入度-1
                    degrees[ord(c)-ord("a")] -= 1
                    if degrees[ord(c)-ord("a")] == 0:
                        Q.append(c)
        # 判断是否有环
        if len(res) != total:
            return ""
        else:
            return res