火星词典

class Solution:    def alienOrder(self, words):        from collections import defaultdict, deque        graph = {ch: set() for w in words for ch in w}        indeg = {ch: 0 for ch in graph}        for a, b in zip(words, words[1:]):            if len(a) > len(b) and a.startswith(b):                return ""            for x, y in zip(a, b):                if x != y:                    if y not in graph[x]:                        graph[x].add(y)                        indeg[y] += 1                    break        q = deque([ch for ch in indeg if indeg[ch] == 0])        ans = []        while q:            ch = q.popleft()            ans.append(ch)            for nxt in graph[ch]:                indeg[nxt] -= 1                if indeg[nxt] == 0:                    q.append(nxt)        return "".join(ans) if len(ans) == len(indeg) else ""

# 1. 定义状态state = init()# 2. 按顺序读输入for x in data:    update(state, x)   # 只做本题允许的安全转移# 3. 从状态里取答案return answer(state)