在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）：如果len（s1）！= len（s2）：返回“否”s1 = s1.lower（）s2 = s2.lower（）如果Counter（s1）== Counter（s2）：返回“是”其他：返回“否”

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

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"

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