我需要能够辨别任意长度的字符串是否大于 1(并且只有小写字母)在基本字符串或模板字符串中具有相同的字符集。
例如,以字符串“aabc”为例:“azbc”和“aaabc”为假,而“acba”为真。
有没有一种快速的方法可以在 python 中执行此操作,而无需跟踪第一个字符串的所有排列,然后将其与测试字符串进行比较?
我需要能够辨别任意长度的字符串是否大于 1(并且只有小写字母)在基本字符串或模板字符串中具有相同的字符集。
例如,以字符串“aabc”为例:“azbc”和“aaabc”为假,而“acba”为真。
有没有一种快速的方法可以在 python 中执行此操作,而无需跟踪第一个字符串的所有排列,然后将其与测试字符串进行比较?
对两个字符串进行排序,然后比较它们:
sorted(str1) == sorted(str2)
如果字符串的长度可能不同,您可能需要先确保这一点以节省时间:
len(str1) == len(str2) and sorted(str1) == sorted(str2)
这是O(n)
解决方案
from collections import Counter
Counter(str1) == Counter(str2)
但是对于合理的值,O(n * log n)
使用的解决方案可能更快sorted
n
这是@Joowani 解决方案的一个变体,它只使用一个字典并且运行得更快(至少在我的机器上):
def cmp4(str1, str2):
if len(str1) != len(str2):
return False
d = collections.defaultdict(int)
for c in str1:
d[c] += 1
for c in str2:
d[c] -= 1
return all(v == 0 for v in d.itervalues())
这是另一个 O(n) 解决方案,比其他解决方案更长但稍快:
def cmp(str1, str2):
if len(str1) != len(str2):
return False
d, d2 = {}, {}
for char in str1:
if char not in d:
d[char] = 1
else:
d[char] += 1
for char in str2:
if char not in d:
return False
if char not in d2:
d2[char] = 1
else:
d2[char] += 1
return d == d2
它基本上与 gnibber 的解决方案做同样的事情(但出于一些奇怪的原因,来自集合库的Counter()似乎很慢)。以下是一些 timeit 结果:
setup = '''
import collections
from collections import Counter
s1 = "abcdefghijklmnopqrstuvwxyz" * 10000
s2 = s1[::-1]
def cmp1(str1, str2):
if len(str1) != len(str2):
return False
d, d2 = {}, {}
for char in str1:
if char not in d:
d[char] = 1
else:
d[char] += 1
for char in str2:
if char not in d:
return False
if char not in d2:
d2[char] = 1
else:
d2[char] += 1
return d == d2
def cmp2(str1, str2):
return len(str1) == len(str2) and sorted(str1) == sorted(str2)
def cmp3(str1, str2):
return Counter(str1) == Counter(str2)
def cmp4(str1, str2):
if len(str1) != len(str2):
return False
d = collections.defaultdict(int)
for c in str1:
d[c] += 1
for c in str2:
d[c] -= 1
return all(v == 0 for v in d.itervalues())
'''
timeit.timeit("cmp1(s1, s2)", setup=setup, number = 100)
8.027034027221656
timeit.timeit("cmp2(s1, s2)", setup=setup, number = 100)
8.175071701324946
timeit.timeit("cmp3(s1, s2)", setup=setup, number = 100)
14.243422195893174
timeit.timeit("cmp4(s1, s2)", setup=setup, number = 100)
5.0937542822775015
此外,当字符串大小很小并且它们实际上具有相同的字符时,David 的解决方案会脱颖而出。
编辑:更新了测试结果
如果您有一个很长的字符串,以下解决方案将有助于 O(n) 时间复杂度。您还可以使用哈希映射/字典代替数组/列表。
s1 = "sjkhdfkaljdhfaldflflad"
s2 = "lsdhfuisfslffsdjdkllja"
if len(s1)!=len(s2):
return False
ds1 = [0] * 26
ds2 = [0] * 26
for i in range(len(s1)):
ds1[ord(s1[i])-ord("a")] +=1
ds2[ord(s2[i])-ord("a")] +=1
return ds1 == ds2
这是另一种方式。通过使用我们忽略最多的“集合”:
if len(set(str1) - set(str2)) == 0:
print "Yes"