Python检查是否存在Anagram的O(n)解决方案

Question

我在检查两个字符串是否是字谜。这个解决方案很简单，但效率不高（olon），我知道我可以使用Collections和Counter，然后比较每个字符的出现情况，但我尽量避免使用任何面试模块。解决这个问题最快的方法是什么？（也许，检查每个字符的出现情况？）在

def check(word1,word2):

    return sorted(word1)==sorted(word2)

Answer 1

这是http://interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/AnAnagramDetectionExample.html的一个不错的选择：

def anagramSolution(s1,s2):

    TABLE_SIZE = 128
    c1 = [0]*TABLE_SIZE
    c2 = [0]*TABLE_SIZE

    for ch in s1:
        pos = ord(ch)
        c1[pos] = c1[pos] + 1

    for ch in s2:
        pos = ord(ch)
        c2[pos] = c2[pos] + 1

    j = 0
    stillOK = True
    while j<TABLE_SIZE and stillOK:
        if c1[j]==c2[j]:
            j = j + 1
        else:
            stillOK = False

    return stillOK

这是在O（n）中运行的。基本上，循环两个字符串，计算每个字母的出现次数。最后，您可以简单地迭代每个字母，确保计数相等。在

正如评论中所指出的，对于unicode，这将很难扩展。如果您希望使用unicode，则可能需要使用字典。在