【python-leetcode269-拓扑排序】火星字典

概述现有一种使用字母的全新语言，这门语言的字母顺序与英语顺序不同。假设，您并不知道其中字母之间的先后顺序。但是，会收到词典中获得一个 不为空的 单词列表。因为是从词典中获得的，所以该单词列表内的单词已经

现有一种使用字母的全新语言，这门语言的字母顺序与英语顺序不同。假设，您并不知道其中字母之间的先后顺序。但是，会收到词典中获得一个 不为空的 单词列表。因为是从词典中获得的，所以该单词列表内的单词已经 按这门新语言的字母顺序进行排序。您需要根据这个输入的列表，还原出此语言中已知的字母顺序。
例如：

输入：

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

输出：

正确的顺序是：“wertf”

 

解题：意思是按照单词的顺序排序了。比如wrt和wrf，wrt排在wrf前面，说明优先级t>f，依次类推则有：

t->f

w->e

r->t

e->r

最终则有顺序：wertf

比较麻烦的就是如何转换成字符间的顺序格式，之后用拓扑排序就好了。

class Solution:                                 def alIEnorder(self,words):        #chars用于获取字母集合        chars=set(''.join(words))        print(chars)        用于存储入度        degrees={x:0 for x in chars}        from collections import defaultdict        用于存储优先级        graph=defaultdict(List)        pair是从上到下两两匹对        for pair in zip(words,words[1:]):            (pair)            x,y依次取出匹对的字母            for x,y in zip(*pair):                (x,y)                if x!=y:                    建立优先级关系                    graph[x].append(y)                    入度增加1                    degrees[y]+=1                    break        (degrees)        (graph)        queue=[]        for i  chars:            if degrees[i] == 0:                queue.append(i)        res=""        while queue:            x=queue.pop(0)            res+=x             graph[x]:                degrees[i]-=1                if degrees[i]==0:                    queue.append(i)        return res*(set(res)==chars)        s=Solution()(s.alIEnorder([  "wrt",wrferettrftt]))

结果：

第二种方法：使用深度优先遍历

(graph)        lis= 0:                lis.append(i)        res= lis:            tmp=[]            for ch  lis:                res+=ch                for c  graph[ch]:                    degrees[c]-=1                    if degrees[c]==0:                        tmp.append(c)                del graph[ch]            lis=tmp        return res if len(res)==len(chars) else ""s=]))

 

参考：https://www.jianshu.com/p/ee280c838f2d

总结

以上是内存溢出为你收集整理的【python-leetcode269-拓扑排序】火星字典全部内容，希望文章能够帮你解决【python-leetcode269-拓扑排序】火星字典所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。