为何Python集合的‘not in’在变位词函数中未正常工作？

原代码的问题 #

• 集合使用错误：将字符串转为集合会丢失字符出现次数的信息，变位词要求两个字符串的字符种类和每个字符的出现次数完全一致，集合只能保证字符种类相同，无法处理次数差异的情况。
• 判断逻辑错误：s1 not in s2的逻辑完全不符合需求。这里s1和s2都是集合，in操作符用于检查某个元素是否存在于集合中，而非判断两个集合是否相等。对于测试用例中的{'x','y'}，它并不是s2的元素（s2的元素是'x'和'y'），因此条件成立，counter被加1，最终返回1。

修复方案 #

方案1：使用collections.Counter统计字符频率（推荐） #

Counter可以便捷地统计每个字符的出现次数，直接比较两个Counter对象即可判断是否为变位词；如果需要计算将后半部分改为前半部分变位词所需的修改次数，也可以通过频率差异计算：

from collections import Counter

def anagram(s):
    if len(s) % 2 == 1:
        return -1
    mid = len(s) // 2
    s1, s2 = s[:mid], s[mid:]
    count1, count2 = Counter(s1), Counter(s2)
    
    # 仅判断是否为变位词，返回0（是）或1（否）
    if count1 == count2:
        return 0
    return 1

    # 若需计算修改字符的数量，替换上面的返回逻辑：
    # match = sum(min(count1[char], count2[char]) for char in count1)
    # return len(s1) - match

print(anagram("xyyx"))  # 输出0，符合预期

方案2：手动实现字符计数（不依赖标准库） #

如果不想使用Counter，可以手动用字典统计字符频率：

def get_char_count(s):
    char_count = {}
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
    return char_count

def anagram(s):
    if len(s) % 2 == 1:
        return -1
    mid = len(s) // 2
    s1, s2 = s[:mid], s[mid:]
    count1 = get_char_count(s1)
    count2 = get_char_count(s2)
    
    if count1 == count2:
        return 0
    return 1

print(anagram("xyyx"))  # 输出0

说明 #

• 若需求是判断两个子串是否为变位词，直接比较字符计数是否相等，返回0（是）或1（否）即可。
• 若需求是计算需要修改多少字符才能让两个子串成为变位词，则使用注释中的修改次数计算逻辑，它会返回需要调整的字符数量。

内容的提问来源于stack exchange，提问作者Ullas B.C