8.15 - hard - 49

269. Alien Dictionary

这道题最最最难点是看出这题是topology sort的解法，如果看出是拓扑排序的话，那么题目就简单多了。

class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        # topology sort
        # 首先第一步要构建graph
        # 找出链表中的顺序
        s = set()
        for word in words:
            for c in word:
                s.add(c)
        graph = {c:set() for c in s} # char to set()
        degree = {c:0 for c in s} # char to int
        # 处理词之间的关系,依据链表的顺序
        for i in range(1, len(words)):
            self.cal(words[i-1], words[i], graph)
        
        # 构造degree
        for key in graph:
            for val in graph[key]:
                degree[val] = degree[val] + 1
        
        # 找出入度为0的加入queue
        queue = []
        for key in degree:
            if degree[key] == 0:
                queue.append(key)
        
        if not queue:
            return ""
        # print graph, degree
        res = ""
        while queue:
            key = queue.pop(0)
            res += key
            for val in graph[key]:
                degree[val] -= 1
                if degree[val] == 0:
                    queue.append(val)
        
        for key, val in degree.iteritems():
            if val != 0:
                return ""
        return res
        
        
    
    def cal(self, w1, w2, graph):
        for i in range(min(len(w1), len(w2))):
            if w1[i] != w2[i]:
                graph[w1[i]].add(w2[i])
                break