python乱序字符串排序的实现方式
作者:梦入玄机 发布时间:2023-08-02 12:14:59
python乱序字符串排序
什么是乱序字符串排序
乱序字符串排序是指一个字符串是另一个字符串的乱序排序,比如apple就是eppal的乱序字符串。
检查
假设字符串由26个小写字符串组成。
1、时间复杂度O(n^2)
解决方案:
判断两个字符串长度是否相等,若不相等返回False,不相等则判断第一个字符串的字符是否在第二个字符串中,如果不在,返回False,如果在则把第二个字符串中查找的位置元素置为None,因为要改变第二个字符串,需把第二个字符串转换为list,代码如下:
def none_sort_str(s1, s2):
s2_list = list(s2)
if len(s1) != len(s2):
return False
else:
for i in range(len(s1)):
for j in range(len(s2_list)):
if s1[i] in s2_list:
s2_list[s2_list.index(s1[i])] = None
break
else:
return False
return True
2、时间复杂度O(n)
解决方案:
判断两个字符串长度是否相等,若不相等返回False,使用计数方式,代码如下:
def none_sort_str2(s1, s2):
a = [0] * 26
b = [0] * 26
for i in range(len(s1)):
index1 = ord(s1[i]) - ord('a')
a[index1] += 1
for i in range(len(s2)):
index2 = ord(s2[i]) - ord('a')
b[index2] += 1
if a == b:
return True
else:
return False
乱序字符串检查算法研究
显示不同量级的算法的一个很好的例子是字符串的乱序检查。乱序字符串是指一个字符串只是另一个字符串的重新排列。
例如,'heart' 和 'earth' 就是乱序字符串。'python' 和 'typhon' 也是。为了简单起见,我们假设所讨论的两个字符串具有相等的长度,并且他们由 26 个小写字母集合组成。我们的目标是写一个布尔函数,它将两个字符串做参数并返回它们是不是乱序。
解法一
思路:将两个字符串都转化成列表,然后遍历其中一个,当前元素在另外一个列表中就把另一个列表的对应元素移除(防止重复干扰)。不存在就返回FALSE,遍历完成返回True
代码参考如下:
str1 = 'hagjen'
str2 = 'ahejng'
def foo(str1,str2):
ls1 = list(str1)
ls2 = list(str2)
for i in ls1:
if i in ls2:
ls2.remove(i)
else:return False
return True
print(foo(str1,str2))
算法复杂度:两层for循环,都是和n线性相关,所以这个算法复杂度为 O(n^2 )。
解法二
两个字符串也都转为列表,然后排序当排序后连个列表相等就返回True,否则FALSE
str1 = 'hagjen'
str2 = 'ahejng'
def foo(str1,str2):
ls1 = list(str1).sort()
ls2 = list(str2) .sort()
return True if ls1==ls2 else False
print(foo(str1,str2))
算法复杂度:咋一看完全没有循环,复杂度好像非常低,但是别忘了排序!排序是python内部实现的,它也需要时间消耗,排序的算法复杂度一般是O(nlog(n)),O(n^2)。所以这种方法不一定比上面的好
解法三
建立两个长度为26的列表,分别遍历两个字符串,分别计数,最后两个列表相同就返回True
def foo(s1,s2):
ls1 = list(s1)
ls2 = list(s2)
count1 = [0 for i in range(26)]
count2 = [0 for i in range(26)]
print(count1)
print(count2)
for i in ls1:
count1[ord(i)-ord('a')] +=1
for i in ls2:
count2[ord(i)-ord('a')] +=1
return True if count1==count2 else False
print(foo('aacf','cfaa'))
时间复杂度:由于没有循环嵌套也没有排序等算法,时间复杂度为2n+26,即O(n)
代码优化:
def is_simlar(s1, s2):
from collections import Counter
return Counter(s1) == Counter(s2)
以上为个人经验,希望能给大家一个参考,也希望大家多多支持脚本之家。
来源:https://blog.csdn.net/qq_36255988/article/details/88290282
猜你喜欢
- 目前任务需要做一个界面程序,PyQt是非常方便的选择,QT丰富的控件以及python方便的编程。近期遇到界面中执行一些后台任务时界面卡死的情
- 内容摘要:“ASP”(Active Server Pages)作为一种典型的服务器端网页设计技术,被广泛地应用在网上银行
- 有这么一个题目,说bt其实也不bt,为了重点突出其中的意图,特意加上了括号:var a = (++Math.P
- 对于在外的游子,每逢佳节倍思亲。而对于996ICU的苦逼程序猿们,最期待的莫过于各种节假日能把自己丢在床上好好休息一下了。这几天各公司都陆续
- 学习了css一段时间,现在对css的一些技巧进行一次小结.希望能对那些刚学习css的新手们带来帮助.一、关于注释在创建xhtml+CSS网站
- 1、引言小 * 丝:鱼哥,你说这就快到圣诞节了,我应该送女神什么礼物呢?小鱼:你的女神又不缺什么礼物,倒不如送点惊喜?小 * 丝:送什么惊喜呢?小鱼
- python的注释方式和C语言、C++、java有所不同python语言中,使用‘#' 来进行注释,其次还有使用 三个引号来进行注释
- 说到排序,我想起一个故事,大意是说唐僧师徒西游美利坚,孙悟空买了本词典,开始逐条背诵单词。他们第一次下美国馆子的时候,不管服务员推荐什么,孙
- ORM模型:ORM模型对于后端开发来说肯定是不陌生的,包括很多后端框架比如django,现在都自带这个模型了ORM(Object Relat
- 在按钮旁边加文字1.打开editor/js/ 两个js文件fckeditorcode_gecko.js fckeditorcode_ie.j
- 论坛有人问起如何获取读取CSS属性值,就写了下面这段兼容各浏览器的获取HTML元素的css属性值函数:function getSt
- 阅读上一篇:Freshow工具使用方法一. eval加密是在网马解密中最常见的,eval在jscript脚本中实际上是一个函数,简单可以理解
- 本文实例讲述了Golang排列组合算法问题之全排列实现方法。分享给大家供大家参考,具体如下:【排列组合问题】一共N辆火车(0<N<
- //-------------------------------------------- // 删除千分点。 //-----------
- 根据微软论坛作者的英文解释,.NET framework 4.0 安装失败回滚貌似是因为“msvcr100_clr0400.d
- 一、lambda关键字的使用方法func=lambda x:x+1print(func(1))#2print(func(2))#3#以上la
- 前言将Selenium程序编写为 .bat 可执行文件,从此一键启动封装好的Selenium程序,省时省力还可以复用,岂不美哉应用场景写好
- 因工作需要研究了支付宝即时到帐接口,并成功应用到网站上,把过程拿出来分享。即时到帐只是支付宝众多商家服务中的一个,表示客户付款,客户用支付宝
- <script> Function.prototype.$bind=function(object) {  
- 方法一通过斜率关系计算,公式如下图:需注意在求斜率时不要出现竖直情况,python计算会报错,但按理说应该可以计算出无穷的,此处先放这吧,等