python - 文字列に同じ文字が含まれているかどうかを確認するにはどうすればよいですか? パイソン

Question

任意の長さ (1 より大きい (小文字のみ)) の文字列が、ベース文字列またはテンプレート文字列内に同じ文字セットを持っているかどうかを識別できる必要があります。

たとえば、文字列 "aabc" を例にとると、"azbc" と "aaabc" は false になり、"acba" は true になります。

最初の文字列のすべての順列を追跡せずに、それをテスト文字列と比較せずに Python でこれを行う簡単な方法はありますか?

Answer 1

2 つの文字列を並べ替えてから比較します。

sorted(str1) == sorted(str2)

文字列の長さが同じでない可能性がある場合は、時間を節約するために最初にそれを確認することをお勧めします。

len(str1) == len(str2) and sorted(str1) == sorted(str2)

Answer 2

これがO(n)解決策です

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

しかし、O(n * log n)使用するソリューションsortedは、n

Answer 3

これは@Joowaniのソリューションのバリエーションで、1つの辞書のみを使用し、さらに高速に実行されます（少なくとも私のマシンでは）：

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())

Answer 4

これは別の 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 のソリューションが最も優れています。

編集：テスト結果を更新しました