专栏首页数据分析与挖掘【python-leetcode269-拓扑排序】火星字典

【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:]):
            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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • python之列表推导和生成器表达式

    这是一般的写法,将字符串中的每一个字符转换称ASCII码,然后存进一个tmp数组。

    绝命生
  • c语言之字符串中字符的存取方法

    绝命生
  • linux之网络适配器修改ip地址的两种方式

    之前使用桥接模式让主机和虚拟机之间进行通信选的是第一个选项:这时要选中自己的网卡名称

    绝命生
  • ASP.NET Core的实时库: SignalR简介及使用

    SignalR是一个.NET Core/.NET Framework的开源实时框架. SignalR的可使用Web Socket, Server Sent Ev...

    solenovex
  • 图解LeetCode第 279 号问题: 完全平方数

    给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

    五分钟学算法
  • 一步步成为linux大神——bash shell中管道和其他命令分隔符的优先级

    一般在bash中,用“|”作为管道,即pipeline,还可以用“;”之类的分隔符连接多个命令。那么下面这个命令的输出是什么呢? date; who |wc 根...

    大神带我来搬砖
  • 赶紧收藏!8张动图了解发动机工作原理

    很直观的还原发动机各部件工作原理,收藏了! 1 发动机运行 ? 2 气缸工作原理 ? 3 进气系统与润滑 ? 4 火花塞 ? 5 正时系统 ? 6 燃油喷射 ?...

    机器人网
  • 赵本山:我的时代还没有结束 | Python告诉你

    【AI科技大本营按】今年春晚的小品好看吗?没有了赵本山的春晚总觉得少了点什么,然而许久不登春晚舞台的本山大叔借着B站的东风证明了「你大爷还是你大爷」。

    AI科技大本营
  • Python进阶学习笔记【干货分享】(二)

    print(id(a))a = 4print(id(a))# 重新赋值之后,内存地址发生改变

    商业新知
  • 干货 | Python进阶系列之学习笔记(二)

    磐创AI

扫码关注云+社区

领取腾讯云代金券