如何优化仅含a/b的字符串列表的最大字符差异计算复杂度

问题描述 #

给定一个包含n个长度为l的字符串的列表，每个字符串的任意位置仅包含字符'a'或'b'，需为每个字符串找出与列表中其他字符串的最大差异数（即对应位置不同字符的数量），并尽可能降低时间复杂度。

示例 #

输入列表：["abaab", "abbbb","babba"]
输出：[5, 3, 5]
解释：

• 第一个字符串与第三个字符串的所有位置字符均不同，差异数为5（最大值）
• 第二个字符串与第三个字符串的差异数为3（最大值）
• 第三个字符串与第一个字符串的差异数为5（最大值）

限制条件 #

• l的上限为20
• n小于100000
• 时间限制15秒

原解法分析 #

你提供的原解法通过统计每个位置上a/b对应的字符串索引，再逐个计算每个字符串与其他所有字符串的差异数，时间复杂度为O(n²·l)。当n=1e5时，n²=1e10，显然无法在时间限制内完成，必须优化。

优化思路 #

由于每个字符串仅包含a/b，且l≤20（二进制位数有限），我们可以利用二进制整数的特性来大幅降低复杂度：

1. 字符串转二进制整数：将每个字符串转换为一个整数（a对应0，b对应1），这样两个字符串的差异数等价于它们对应整数的汉明距离（二进制中不同位的数量）。
2. 最大差异数的本质：对于整数x，与其汉明距离最大的数是它的补数（mask ^ x，其中mask是l位全1的整数），此时汉明距离为l（最大可能值）。如果补数存在，直接返回l；否则，找与补数汉明距离最小的存在数，此时差异数为l减去该汉明距离。
3. BFS快速查找近邻：用BFS按汉明距离从小到大枚举补数的近邻，找到第一个存在的数即可，避免不必要的计算。
4. 哈希集合加速查询：将所有转换后的整数存入哈希集合，实现O(1)的存在性查询。

该方法的时间复杂度为O(n·l + n·K)，其中K是每个字符串平均枚举的候选数（远小于n），整体复杂度远优于O(n²·l)，满足面试官要求的O(l·n·logn)（甚至更优）。

代码实现 #

from collections import deque

def str_to_int(s):
    """将a/b字符串转换为二进制整数，a→0，b→1"""
    x = 0
    for c in s:
        x <<= 1
        if c == 'b':
            x |= 1
    return x

def max_diff_for_str(x, seen, l, mask):
    z = mask ^ x  # x的补数（对应字符串的每个字符取反）
    if z in seen:
        return l
    
    visited = set()
    q = deque()
    q.append((z, 0))
    visited.add(z)
    
    while q:
        current, dist = q.popleft()
        # 生成所有汉明距离+1的候选数
        for i in range(l):
            candidate = current ^ (1 << i)
            if candidate in seen:
                return l - (dist + 1)
            if candidate not in visited:
                visited.add(candidate)
                q.append((candidate, dist + 1))
    
    # 所有字符串都是x本身，差异数为0
    return 0

def compute_max_differences(strings):
    if not strings:
        return []
    
    l = len(strings[0])
    mask = (1 << l) - 1  # l位全1的掩码
    seen = set()
    int_list = []
    
    # 预处理：转换所有字符串为整数并存入集合
    for s in strings:
        x = str_to_int(s)
        int_list.append(x)
        seen.add(x)
    
    # 计算每个字符串的最大差异数
    return [max_diff_for_str(x, seen, l, mask) for x in int_list]

# 测试示例
strings = ["abaab", "abbbb","babba"]
print(compute_max_differences(strings))  # 输出: [5, 3, 5]

代码说明 #

• str_to_int：将字符串转换为二进制整数，简化后续位运算操作。
• max_diff_for_str：针对单个整数x，通过BFS查找与x差异最大的字符串对应的整数，返回最大差异数。
• compute_max_differences：预处理所有字符串，调用max_diff_for_str生成最终结果。

内容的提问来源于stack exchange，提问作者Arjun Senthil