Python 在 O(n) 解决方案中检查 Anagram

Question

我正在尝试检查 2 个字符串是否是字谜词。这个解决方案很简单，但效率不高(Ologn)我知道我可以使用集合和计数器，然后比较每个字符的出现，但我试图避免任何面试模块。解决这个问题最快的方法是什么？ (也许，检查每个字符的出现情况？)

def check(word1,word2):

    return sorted(word1)==sorted(word2)

Answer 1

您的代码甚至没有返回正确的值。该单行代码的复杂度为 O(n log n):

return sorted(word1) == sorted(word2)

对于 O(n) 解决方案，您可以计算所有字符:

from collections import Counter
# ...
def check(a, b)
  return Counter(a) == Counter(b)

如果没有集合，它会更长:

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):创建一个字典，其中任一单词中出现的所有字符作为键设置为 0。
• for c in a: chars[c] += 1:这将迭代 a 并计算其中每个字符的出现次数。 chars 现在包含单独字符的计数(以及 b 中字符的一些零，但 a 中没有)
• for c in b: chars[c] -= 1:与之前基本相同，但会从 中减去 b 的字符数字符
• return not any(chars.values()):chars['h'] == 0当且仅当a并且b 具有相同数量的 'h'。此行检查 chars 是否仅包含零作为值，这意味着所有字符在两个输入中都具有相同的计数。 (如果序列中存在任何真值，any 就会返回。0 为假值，其他所有整数均为真值。)

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