6

我需要能够辨别任意长度的字符串是否大于 1（并且只有小写字母）在基本字符串或模板字符串中具有相同的字符集。

例如，以字符串“aabc”为例：“azbc”和“aaabc”为假，而“acba”为真。

有没有一种快速的方法可以在 python 中执行此操作，而无需跟踪第一个字符串的所有排列，然后将其与测试字符串进行比较？

4

6 回答 6

18

对两个字符串进行排序，然后比较它们：

sorted(str1) == sorted(str2)

如果字符串的长度可能不同，您可能需要先确保这一点以节省时间：

len(str1) == len(str2) and sorted(str1) == sorted(str2)
于 2013-08-20T00:51:04.037 回答
5

这是O(n)解决方案

from collections import Counter
Counter(str1) == Counter(str2)

但是对于合理的值，O(n * log n)使用的解决方案可能更快sortedn

于 2013-08-20T00:52:56.163 回答
1

这是@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())
于 2013-08-20T02:16:52.680 回答
0

这是另一个 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 的解决方案会脱颖而出。

编辑：更新了测试结果

于 2013-08-20T02:06:02.207 回答
0

如果您有一个很长的字符串，以下解决方案将有助于 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
于 2022-02-02T17:59:15.800 回答
-1

这是另一种方式。通过使用我们忽略最多的“集合”：

if len(set(str1) - set(str2)) == 0:
    print "Yes"
于 2018-04-15T08:55:09.120 回答