Python 官方文档：入门教程 => 点击学习
目录python乱序字符串排序什么是乱序字符串排序检查乱序字符串检查算法研究 解法一解法二解法三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 True2、时间复杂度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)以上为个人经验，希望能给大家一个参考，也希望大家多多支持编程网。
--结束END--
本文标题: python乱序字符串排序的实现方式
本文链接: https://lsjlt.com/news/120860.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
2024-03-01
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
官方手机版
微信公众号
商务合作
0