python - 在线性时间内检查字谜字符串

Question

因此，给定两个字符串的输入，我有以下线性时间解决方案来检查一个字符串是否是另一个字符串的变位词。我想要一个更简洁和 pythonic 的线性时间解决方案。

def perm_check(str1,str2):

    if len(str1)!=len(str2):
        return False

    d1,d2={},{}

    for i in range(len(str1)):

        l1=str1[i]
        l2=str2[i]

        if l1 in d1:
            d1[l1]+=1
        else:
            d1[l1]=1


        if l2 in d2:
            d2[l2]+=1
        else:
            d2[l2]=1


    for letter in d1:

        if letter not in d2:
            return False

        if d1[letter] != d2[letter]:

            return False        

    return True


print(perm_check("stab","bats"))

我该如何优化它？

Answer 1

你可以使用 python collections.Counter类来做到这一点。基本上，在变位词中，两个字符串中每个字符的数量必须相同，因此您只需要计算两个字符串中每个字符的字符数，然后比较它们。 Counter 类将为您创建字典，您可以直接比较它们。

from collections import Counter

def is_anagram(string1, string2):
    return Counter(string1) == Counter(string2)

结果:

>>> is_anagram("helper", "perhel")
True
>>> is_anagram("helper", "perhe")
False
>>> is_anagram("helper", "perhes")
False