from heapq import*classSolution:defalienOrder(self,words):# Construct Graph in_degree ={char:0for word in words for char in word} neighbors = collections.defaultdict(list)for pos inrange(len(words) -1):for i inrange(min(len(words[pos]), len(words[pos+1]))): pre,next= words[pos][i], words[pos+1][i]if pre !=next:# 前后两个单词第一个不一样的字母 in_degree[next]+=1 neighbors[pre].append(next)break# Topological Sort heap = [ch for ch in in_degree if in_degree[ch]==0]heapify(heap) order = []while heap:for _ inrange(len(heap)): ch =heappop(heap) order.append(ch)for child in neighbors[ch]: in_degree[child]-=1if in_degree[child]==0:heappush(heap, child)# order is invalidiflen(order)!=len(in_degree):return""return''.join(order)
classSolution:defisAlienSorted(self,words: List[str],order:str) ->bool: mydict ={v:i for i, v inenumerate(order)} words_order = []for word in words: words_order.append([mydict[char] for char in word])# for w1, w2 in zip(words, words[1:]): # if w1 > w2:# return Falsereturnall(w1 <= w2 for w1, w2 inzip(words_order, words_order[1:]))