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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【python-leetcode269-拓扑排序】火星字典，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2105字，纯文字阅读大概需要4分钟。

内容图文

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

输入：

[
  "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:]):
            print(pair)
            #x,y依次取出匹对的字母
            for x,y in zip(*pair):
                print(x,y)
                if x!=y:
                    #建立优先级关系
                    graph[x].append(y)
                    #入度增加1
                    degrees[y]+=1
                    break
        print(degrees)
        print(graph)
        queue=[]
        for i in chars:
            if degrees[i] == 0:
                queue.append(i)
        res=""
        while queue:
            x=queue.pop(0)
            res+=x
            for i in graph[x]:
                degrees[i]-=1
                if degrees[i]==0:
                    queue.append(i)
        return res*(set(res)==chars)        

s=Solution()
print(s.alienOrder([
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]))

结果：

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

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:]):
            print(pair)
            #x,y依次取出匹对的字母
            for x,y in zip(*pair):
                print(x,y)
                if x!=y:
                    #建立优先级关系
                    graph[x].append(y)
                    #入度增加1
                    degrees[y]+=1
                    break
        print(degrees)
        print(graph)
        lis=[]
        for i in chars:
            if degrees[i] == 0:
                lis.append(i)
        res=""
        while lis:
            tmp=[]
            for ch in lis:
                res+=ch
                for c in 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=Solution()
print(s.alienOrder([
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]))

 

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

内容总结

以上是互联网集市为您收集整理的【python-leetcode269-拓扑排序】火星字典全部内容，希望文章能够帮你解决【python-leetcode269-拓扑排序】火星字典所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---