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，则可能需要使用字典。在

Answer 2

如果没有输入，我会这样写：

def count_occurences(mystring):
    occs = {}
    for char in mystring:
        if char in occs:
            occs[char] += 1
        else:
            occs[char] = 1
    return occs

def is_anagram(str1, str2):
    return count_occurences(str1) == count_occurences(str2)

或者，如果可以使用导入，而不是Counter，请使用defaultdict：

^{pr2}$

Answer 3

你的代码甚至没有返回正确的值。这一行是O（n logn）：

return sorted(word1) == sorted(word2)

对于O（n）解决方案，可以对所有字符进行计数：

^{pr2}$

如果没有收藏，它会更长：

def check(a, b):
    chars = dict.fromkeys(a + b, 0)
    for c in a:
        chars[c] += 1
    for c in b:
        chars[c] -= 1
    return not any(chars.values())

此代码执行以下操作：

• chars = dict.fromkeys(a + b, 0)：创建一个dict，它将两个单词中出现的所有字符都设置为0。在
• for c in a: chars[c] += 1：这将迭代a并计算其中每个字符的出现次数。chars现在包含独立字符的计数（对于b而不是a中的字符，还有一些零）
• for c in b: chars[c] -= 1：与之前一样，但是这将从chars中减去{}的字符数
• return not any(chars.values())：chars['h'] == 0当且仅当a和{}具有相同数量的'h'。这行检查chars是否只有零作为值，这意味着所有字符在两个输入中都有相同的计数。（asany返回序列中是否有任何真实值。0是假的，其他整数都是真的。）

两个列表都被迭代一次。假设字典的访问时间为O（1），则整个算法在O（n）时间内运行（其中n是输入的总长度）。空间复杂度也是O（n）（所有字符都可以是不同的）。当他们问你复杂性时，不要犯这个错误。这不是必要的时间复杂性。在