Python中高效比较含重复字符的大型无序字符串方法问询

要判断两个（或多个）含重复字符的大型无序字符串是否"相同"（即字符种类和出现次数完全一致），sorted()方法因O(n log n)的时间复杂度在处理长字符串时效率偏低，而set()无法统计字符出现次数，因此可以采用以下几种优化方案：

方案1：使用collections.Counter（简洁高效） #

Python内置的Counter专门用于统计可哈希对象的频次，时间复杂度为O(n)，代码简洁易读：

from collections import Counter

def are_strings_equal(s1, s2):
    # 先判断长度，长度不同直接返回False，避免无效计算
    if len(s1) != len(s2):
        return False
    return Counter(s1) == Counter(s2)

• 优势：无需手动实现统计逻辑，内置库优化到位，对于长度数千的字符串完全够用；
• 关键优化：提前检查长度可终止不必要的统计操作。

方案2：手动数组统计（极致性能） #

由于约束条件限定字符仅为英文字母，我们可以用固定大小的数组统计频次，避免哈希表的额外开销，还能提前终止判断：

def are_strings_equal(s1, s2):
    if len(s1) != len(s2):
        return False
    
    # 区分大小写：26个大写+26个小写，共52个位置；若不区分可改为26个并统一转大小写
    char_counts = [0] * 52

    # 统计第一个字符串的字符频次
    for char in s1:
        if char.isupper():
            index = ord(char) - ord('A')
        else:
            index = 26 + ord(char) - ord('a')
        char_counts[index] += 1
    
    # 遍历第二个字符串，递减频次并实时检查
    for char in s2:
        if char.isupper():
            index = ord(char) - ord('A')
        else:
            index = 26 + ord(char) - ord('a')
        char_counts[index] -= 1
        # 若出现负数，说明该字符在s2中出现次数多于s1，直接返回False
        if char_counts[index] < 0:
            return False
    
    # 检查所有频次是否归零
    return all(count == 0 for count in char_counts)

• 优势：数组访问是O(1)操作，无哈希冲突风险，且在第二个循环中可提前终止，性能比Counter更优；
• 适用场景：对性能要求极高，且明确字符范围的场景。

方案3：预计算哈希值（多字符串重复比较） #

如果需要多次比较多个字符串，可以预先计算每个字符串的"频次哈希值"，后续直接比较哈希值即可：

def calculate_freq_hash(s, case_sensitive=True):
    base = 911382629  # 选择大质数作为基数
    mod = 10**18 + 3  # 大模数减少哈希碰撞概率
    hash_value = 0
    
    # 初始化频次数组
    if case_sensitive:
        count = [0] * 52
        for char in s:
            if char.isupper():
                idx = ord(char) - ord('A')
            else:
                idx = 26 + ord(char) - ord('a')
            count[idx] += 1
    else:
        count = [0] * 26
        for char in s.lower():
            idx = ord(char) - ord('a')
            count[idx] += 1
    
    # 将频次数组转换为哈希值
    for num in count:
        hash_value = (hash_value * base + num) % mod
    return hash_value

def are_strings_equal(s1, s2):
    if len(s1) != len(s2):
        return False
    return calculate_freq_hash(s1) == calculate_freq_hash(s2)

• 优势：一次计算哈希值后，后续比较仅需O(1)时间，适合需要反复比较同一批字符串的场景；
• 注意：需选择合适的基数和模数降低哈希碰撞概率，若对准确性要求极高，可结合前两种方案验证。

内容的提问来源于stack exchange，提问作者Faisal Khan