python亂序字符串排序的實現(xiàn)方式
python亂序字符串排序
什么是亂序字符串排序
亂序字符串排序是指一個字符串是另一個字符串的亂序排序,比如apple就是eppal的亂序字符串。
檢查
假設(shè)字符串由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' 也是。為了簡單起見,我們假設(shè)所討論的兩個字符串具有相等的長度,并且他們由 26 個小寫字母集合組成。我們的目標是寫一個布爾函數(shù),它將兩個字符串做參數(shù)并返回它們是不是亂序。
解法一
思路:將兩個字符串都轉(zhuǎn)化成列表,然后遍歷其中一個,當前元素在另外一個列表中就把另一個列表的對應(yīng)元素移除(防止重復干擾)。不存在就返回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 + requests實現(xiàn)發(fā)送HTTP請求
這篇文章主要介紹了如何基于Python + requests實現(xiàn)發(fā)送HTTP請求,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-01-01python如何把字符串類型list轉(zhuǎn)換成list
這篇文章主要介紹了python如何吧字符串類型list轉(zhuǎn)換成list,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-02-02python?matplotlib畫圖時坐標軸重疊顯示不全和圖片保存時不完整的問題解決
最近工作中遇到了matplotlib保存圖片坐標軸不完整的問題,所以這篇文章主要給大家介紹了關(guān)于python?matplotlib畫圖時坐標軸重疊顯示不全和圖片保存時不完整問題的解決方法,需要的朋友可以參考下2022-07-07Python日期和時間戳的轉(zhuǎn)換的實現(xiàn)方式
Python中日期和時間的處理涉及到time和datetime模塊,time模塊可實現(xiàn)時間戳與格式化時間字符串的轉(zhuǎn)換,而datetime模塊則提供更加直接易用的接口,本文詳細給大家介紹了Python日期和時間戳的轉(zhuǎn)換的實現(xiàn)方式,需要的朋友可以參考下2024-10-10