python亂序字符串排序的實現(xiàn)方式
python亂序字符串排序
什么是亂序字符串排序
亂序字符串排序是指一個字符串是另一個字符串的亂序排序，比如apple就是eppal的亂序字符串。
檢查
假設字符串由26個小寫字符串組成。
1、時間復雜度O(n^2)
解決方案：
判斷兩個字符串長度是否相等，若不相等返回False，不相等則判斷第一個字符串的字符是否在第二個字符串中，如果不在，返回False，如果在則把第二個字符串中查找的位置元素置為None，因為要改變第二個字符串，需把第二個字符串轉(zhuǎn)換為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，使用計數(shù)方式，代碼如下：
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 個小寫字母集合組成。我們的目標是寫一個布爾函數(shù)，它將兩個字符串做參數(shù)并返回它們是不是亂序。
解法一
思路：將兩個字符串都轉(zhuǎn)化成列表，然后遍歷其中一個，當前元素在另外一個列表中就把另一個列表的對應元素移除（防止重復干擾）。不存在就返回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循環(huán)，都是和n線性相關(guān)，所以這個算法復雜度為 O(n^2 )。
解法二
兩個字符串也都轉(zhuǎn)為列表，然后排序當排序后連個列表相等就返回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))
算法復雜度：咋一看完全沒有循環(huán)，復雜度好像非常低，但是別忘了排序！排序是python內(nèi)部實現(xiàn)的，它也需要時間消耗，排序的算法復雜度一般是O(nlog（n）)，O(n^2)。所以這種方法不一定比上面的好
解法三
建立兩個長度為26的列表，分別遍歷兩個字符串，分別計數(shù)，最后兩個列表相同就返回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'))時間復雜度：由于沒有循環(huán)嵌套也沒有排序等算法，時間復雜度為2n+26，即O(n)
代碼優(yōu)化：
def is_simlar(s1, s2): ? ? from collections import Counter ? ? return Counter(s1) == Counter(s2)
以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要介紹了初步解析Python下的多進程編程,使用多進程編程一直是Python編程當中的重點和難點,需要的朋友可以參考下2015-04-04
使用Python實現(xiàn)Excel文件轉(zhuǎn)換為SVG格式
SVG（Scalable Vector Graphics）是一種基于XML的矢量圖像格式,這種格式在Web開發(fā)和其他圖形應用中非常流行,提供了一種高效的方式來呈現(xiàn)復雜的矢量圖形,本文將介紹如何使用Python轉(zhuǎn)換Excel文件為SVG格式,需要的朋友可以參考下2024-07-07
這篇文章主要介紹了Django中的Model操作表的實現(xiàn),小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-07-07
Python使用matplotlib實現(xiàn)的圖像讀取、切割裁剪功能示例
這篇文章主要介紹了Python使用matplotlib實現(xiàn)的圖像讀取、切割裁剪功能,結(jié)合實例形式分析了Python基于matplotlib操作圖片的加載、讀取、坐標控制及裁剪相關(guān)操作技巧,需要的朋友可以參考下2018-04-04
這篇文章主要介紹了Python發(fā)送郵件測試報告操作,結(jié)合實例形式較為詳細的分析了Python郵件發(fā)送相關(guān)模塊使用及操作注意事項,需要的朋友可以參考下2018-12-12
這篇文章主要介紹了python實現(xiàn)KNN近鄰算法的方法，幫助大家更好的利用python進行機器學習，感興趣的朋友可以了解下2020-12-12
基于Python實現(xiàn)PDF轉(zhuǎn)換文件格式
這篇文章主要為大家詳細介紹了如何基于Python實現(xiàn)PDF轉(zhuǎn)換文件格式,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下2025-01-01
這篇文章主要介紹了在Python的Django框架中為代碼添加注釋的方法,需要的朋友可以參考下2015-07-07
下面小編就為 大家?guī)硪黄猵ython生成式的send()方法(詳解)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-05-05
Django User 模塊之 AbstractUser 擴展詳解
這篇文章主要介紹了Django User 模塊之 AbstractUser 擴展詳解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-03-03