日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

python亂序字符串排序的實現方式_python

作者：夢入玄機 ? 更新時間： 2022-12-04 編程語言

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)

原文鏈接：https://blog.csdn.net/qq_36255988/article/details/88290282

欄目分類
最近更新