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 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)

以上为个人经验，希望能给大家一个参考，也希望大家多多支持我们。

赞 (0)

相关推荐

  • Python使用random.shuffle()打乱列表顺序的方法

    Python的random.shuffle()函数可以用来乱序序列,它是在序列的本身打乱,而不是新生成一个序列. 示例: from random import shuffle x = [[i] for i in range(10)] shuffle(x) shuffle()返回的是None,列表x的顺序被打乱. 以上这篇Python使用random.shuffle()打乱列表顺序的方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

  • Python实现乱序文件重新命名编号

    Python实现乱序文件重新命名编号

    目录 获取文件列表 筛选视频文件 批量重命名 人生苦短,快学Python! 最近有位读者朋友遇到了一个小问题,私聊找小五答疑.感觉也会有其他同学会遇到,所以干脆分享出来. 如下图所示,在本地文件夹中有这样一堆视频文件,在这种情况下并不是乱序的. 但是将其上传到网盘中后,就会经常变成乱序.即它们会按照1.10.11.2.20这样排序,并不方便我们按顺序去依次观看. 所以我们希望能够给它们在本地重新命名编号,比如可以按照001.002.003···.020这样排序,就可以避免上面这种尴尬的情况了.

  • python json load json 数据后出现乱序的解决方案

    众所周知:python json 可以转换的json字符串,但是在将其转换为字典时,出现了乱序 字典是一个散列结构,亦即他自身根据key进行排序,无法保证顺序 import json jsonstr = '{"username":"string","age":"int","income":"float","createdTime":"date"}'

  • python乱序字符串排序的实现方式

    目录 python乱序字符串排序 什么是乱序字符串排序 检查 乱序字符串检查算法研究 解法一 解法二 解法三 python乱序字符串排序 什么是乱序字符串排序 乱序字符串排序是指一个字符串是另一个字符串的乱序排序,比如apple就是eppal的乱序字符串. 检查 假设字符串由26个小写字符串组成. 1.时间复杂度O(n^2) 解决方案: 判断两个字符串长度是否相等,若不相等返回False,不相等则判断第一个字符串的字符是否在第二个字符串中,如果不在,返回False,如果在则把第二个字符串中查找的

  • python中路径字符串斜杠替换方式

    目录 python路径字符串斜杠替换 python将双斜杠替换为单斜杠 字符串问题 问题处理 总结 python路径字符串斜杠替换 以下是单反斜杠替换成正斜杠和双反斜杠的方法. # 单反斜杠 originPath = r'D:\图片\Zbtv1.jpg' # 加上r后变为原始字符串,则不会对字符串进行转义 # 替换成正斜杠 nowPath1 = originPath.replace('\\','/') # 替换为D:/图片/Zbtv1.jpg # 替换成双反斜杠 nowPath2 = origi

  • python字符串排序方法

    本文以实例形式简述了Python实现字符串排序的方法,是Python程序设计中一个非常实用的技巧.分享给大家供大家参考之用.具体方法如下: 一般情况下,python中对一个字符串排序相当麻烦: 一.python中的字符串类型是不允许直接改变元素的.必须先把要排序的字符串放在容器里,如list. 二.python中的list容器的sort()函数没返回值. 所以在python中对字符串排序往往需要好几行代码. 具体实现方法如下: >>> s = "string" >

  • JavaScript数组的快速克隆(slice()函数)和数组的排序、乱序和搜索(sort()函数)

    JavaScript中对变量的操作都是通过引用方式,而对数组也一样. 前两天想要对一个数组进行复制,一直苦于找不到办法(遍历的方法俺是绝对不采用的) 无意中拿起<JavaScript权威指南>翻了翻数组的操作函数,发现了slice()函数. slice()原来是用来截取数组中的一部分,这里我用它来复制数组,它的格式如下: array.slice(start, end) 如果省略了end参数,则切分的数组包含从start开始到数组结束的所有元素. 现在要用它来复制数组,就一行,呵呵: var n

  • python生成不重复随机数和对list乱序的解决方法

    andom.sample(list, n)即是从list中随机选取n个不同的元素 # -*- coding: utf-8 -*- import random # 从一个list中随机挑选5个 list = [12, 23, 13, 14, 78, 234, 123, 12345] randomlist = random.sample(list, 5) print randomlist # 在range(10)中随机生成5个不重复的数,可以作为随机下标集合,然后到list中取数 len = lis

  • 解决python中os.listdir()函数读取文件夹下文件的乱序和排序问题

    1. os.listdir()概述 os.listdir() 方法用于返回指定的文件夹包含的文件或文件夹的名字的列表. 例如: dir ='F:/Home_01/img'#当前目录 filenames=os.listdir(dir)#filenames存储dir下的所有文件名. 注意:os.listdir()返回的文件名不一定是顺序的,也就是说结果是不固定的,如下图,则filenames[0]有可能为'22.jpg',而不是我们所希望的'11.jpg'. 解决办法: filenames=os.l

  • python对数组进行排序,并输出排序后对应的索引值方式

    废话不多说,直接上代码吧! # -*- coding: cp936 -*- import numpy as np #一维数组排序 arr = [1, 3, 5, 2, 4, 6] arr = np.array(arr) print arr print np.sort(arr)#或print np.sort(arr,axis=None) print (np.argsort(arr)) # 正序输出索引,从小到大 print (np.argsort(-arr)) # 逆序输出索引,从大到小 输出结果

  • JavaScript中数组的排序、乱序和搜索实现代码

    1. 排序: 默认的sort()按字符编码排序的: 复制代码 代码如下: <script type="text/javascript"> <!-- var testArray=[3,324,5345,6546,134,5654,665]; testArray.sort(); alert(testArray); //--> </script> 现在要让它按照数值大小排序: 复制代码 代码如下: <script type="text/ja

  • Python 字符串换行的多种方式

    第一种: x0 = '<?xml version="1.0"?>' \ '<ol>' \ ' <li><a href="/python" rel="external nofollow" rel="external nofollow" rel="external nofollow" rel="external nofollow" >Pytho

随机推荐