Python实现乱序字符串检查的三种算法及复杂度分析
本文深入解析Python中判断两个字符串是否为乱序排列的多种实现方式。从基础的遍历移除法（O(n^2)）到排序比较法（O(nlogn)），再到基于字符计数的线性时间复杂度解法（O(n)），详细对比了各方案的时间复杂度与代码实现。文章还探讨了利用Counter优化计数的技巧，帮助开发者根据实际场景选择最优算法。
Python实现乱序字符串排序
什么是乱序字符串排序
所谓乱序字符串，指的是一个字符串恰好是另一个字符串的字符重排结果。例如，'apple' 与 'eppal' 互为乱序字符串，因为它们包含相同的字符且数量一致。
检查
在讨论具体算法前，通常假设字符串仅由26个小写英文字母组成，且两个待比较字符串长度相等。
1、时间复杂度O(n^2)
解决方案：
首先判断两个字符串的长度是否相等，若不相等则直接返回False。若长度相等，则遍历第一个字符串的每个字符，检查其是否存在于第二个字符串中。若不存在，返回False；若存在，则将该字符在第二个字符串中的对应位置标记为None（需先将第二个字符串转换为列表以便修改）。代码如下：
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 True2、时间复杂度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(nlogn) 或 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)以上为个人经验总结，希望能给大家提供一个参考，也希望大家多多支持本站。
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
