在Python中检查字符串是否为字谜时，在时间和空间复杂度方面哪个更好？

Question

以下是我的相同实现：1）通过保留计数来使用字典：

def anagram(s1,s2):
if len(s1)!=len(s2):
    return "No"
count={}
for let in s1:
    if let not in count:
        count[let]=1
    else:
        count[let]+=1
for let2 in s2:
    if let2 in count:
        count[let2]-=1
    else:
        count[let2]=1
for k in count:
    if count[k]!=0:
        return "No"
return "yes"

2）使用内置的排序功能并比较字符串：

def anagram2(s1,s2):
if len(s1)!=len(s2):
    return "no"
s1=str(sorted(s1))
s2=str(sorted(s2))
if s1.lower()==s2.lower():
    return "yes"
else:
    return "No"

3）使用集合中的COunter：

from collections import Counter
def anagram3(s1,s2):
    if len(s1)!=len(s2):
       return "no"
    s1=s1.lower()
    s2=s2.lower()
    if Counter(s1)==Counter(s2):
       return "Yes"
    else:
       return "no"

两者之间哪个时间复杂度更高？还有其他方法可以使这个字谜问题更有效吗？如果是，请让我知道。

Answer 1

第一种实现方式效率更高：仅需要O(s1+s2)。在第二种实现中，您使用sorted函数，即O(nlogn)（请参见：What is the complexity of this python sort method?），因此总计为O(s1*log(s1)+s2*log(s2))

编辑：正如其他人在评论中所说，collections.Counter是最简单的方法：

from collections import Counter
if Counter(s1) == Counter(s2):
     return "yes"
return "no"

（（不确定是否要区分大小写）

Answer 2

[没有一种方法比第一个运行O(n)的方法渐近有效。第二种方法在O(n log n)中运行。

在O(n)类算法中，您可以在某些情况下添加一些短路以提高性能，甚至可以将其写入一个循环中（这允许其他一些短路，但代价是其他一些短路） ，例如：

def is_anagram_1loop(a, b):
    if len(a) != len(b):
        return False
    support = {}
    for x, y in zip(a, b):
        if x == y:
            continue
        if x not in support:
            support[x] = 1
        else:
            support[x] += 1
        if y not in support:
            support[y] = 1
        else:
            support[y] -= 1
    for k, v in support.items():
        if v:
            return False
    return True

def is_anagram_2loops(a, b):
    if len(a) != len(b):
        return False
    support = {}
    for x in a:
        if x not in support:
            support[x] = 1
        else:
            support[x] += 1
    for y in b:
        if y not in support:
            # it should have beed found while looping through `a`
            return False
        else:
            support[y] -= 1
    for k, v in support.items():
        if v:
            return False
    return True

---

但是，从速度上来说，使用collections.Counter()通常要快得多，因为两个循环都是隐式完成的：

import collections


def is_anagram_counter(a, b):
    if len(a) == len(b):
        return collections.Counter(a) == collections.Counter(b)
    else:
        return False

上述缺点可能是更大的内存消耗。