python乱序字符串排序的实现方式
梦入玄机 人气:0python乱序字符串排序
什么是乱序字符串排序
乱序字符串排序是指一个字符串是另一个字符串的乱序排序,比如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)
以上为个人经验,希望能给大家一个参考,也希望大家多多支持。
加载全部内容