子字符串异或查询

标签: 位运算 数组 哈希表 字符串

难度: Medium

给你一个 二进制字符串 s 和一个整数数组 queries ，其中 queries[i] = [firsti, secondi] 。

对于第 i 个查询，找到 s 的 最短子字符串 ，它对应的 十进制值 val 与 firsti 按位异或 得到 secondi ，换言之，val ^ firsti == secondi 。

第 i 个查询的答案是子字符串 [lefti, righti] 的两个端点（下标从 0 开始），如果不存在这样的子字符串，则答案为 [-1, -1] 。如果有多个答案，请你选择 lefti 最小的一个。

请你返回一个数组 ans ，其中 ans[i] = [lefti, righti] 是第 i 个查询的答案。

子字符串 是一个字符串中一段连续非空的字符序列。

示例 1：

输入：s = "101101", queries = [[0,5],[1,2]]
输出：[[0,2],[2,3]]
解释：第一个查询，端点为 [0,2] 的子字符串为 "101" ，对应十进制数字 5 ，且 5 ^ 0 = 5 ，所以第一个查询的答案为 [0,2]。第二个查询中，端点为 [2,3] 的子字符串为 "11" ，对应十进制数字 3 ，且 3 ^ 1 = 2 。所以第二个查询的答案为 [2,3] 。

示例 2：

输入：s = "0101", queries = [[12,8]]
输出：[[-1,-1]]
解释：这个例子中，没有符合查询的答案，所以返回 [-1,-1] 。

示例 3：

输入：s = "1", queries = [[4,5]]
输出：[[0,0]]
解释：这个例子中，端点为 [0,0] 的子字符串对应的十进制值为 1 ，且 1 ^ 4 = 5 。所以答案为 [0,0] 。

提示：

  • 1 <= s.length <= 104
  • s[i] 要么是 '0' ，要么是 '1' 。
  • 1 <= queries.length <= 105
  • 0 <= firsti, secondi <= 109

Submission

运行时间: 107 ms

内存: 57.3 MB

class Solution:
    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:
        n, m = len(s), {}
        if (i := s.find('0')) >= 0:
            m[0] = (i, i)  # 这样下面就可以直接跳过 '0' 了，效率更高
        for l, c in enumerate(s):
            if c == '0': continue
            x = 0
            for r in range(l, min(l + 30, n)):
                x = (x << 1) | (ord(s[r]) & 1)
                if x not in m:
                    m[x] = (l, r)
        NOT_FOUND = (-1, -1)
        return [m.get(x ^ y, NOT_FOUND) for x, y in queries]

Explain

这个题解的思路基于预处理和哈希表的使用。首先，题解构建一个哈希表来存储所有可能的子字符串及其对应的起始和结束位置。算法首先检测字符串中的第一个'0'字符，并记录其位置（只记录第一个零是因为任何以0开始的子字符串的十进制值都是0）。然后，对于字符串中的每个'1'开始的位置，算法计算以该位置开始的所有可能长度（最长为30位，足以表示所有整数）的子字符串的十进制值，并将这些值及其对应的起始和结束位置存储在哈希表中。最后，对于每个查询，算法通过计算查询的异或值是否存在于哈希表中来直接返回答案，从而避免了多次计算。

时间复杂度: O(n + q)

空间复杂度: O(n + q)

class Solution:
    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:
        n, m = len(s), {}
        # 查找字符串中的第一个'0'并记录其位置
        if (i := s.find('0')) >= 0:
            m[0] = (i, i)  # 记录第一个0的位置，因为0异或任何数都是那个数
        for l, c in enumerate(s):
            if c == '0': continue  # 跳过'0'以提高效率
            x = 0
            # 从当前位置开始，计算最多30位的子字符串的十进制值
            for r in range(l, min(l + 30, n)):
                x = (x << 1) | (ord(s[r]) & 1)  # 计算子字符串的二进制到十进制的转换
                if x not in m:
                    m[x] = (l, r)  # 将子字符串的值和对应的位置存储在哈希表中
        NOT_FOUND = (-1, -1)
        # 对每个查询计算异或结果，并查找哈希表
        return [m.get(x ^ y, NOT_FOUND) for x, y in queries]

Explore

在处理二进制字符串时，以'0'开始的子字符串在二进制转十进制计算中，较长的前导0对值没有贡献，因此它们通常不会影响最终的十进制值，直到出现第一个'1'。例如，子字符串'0001'与'1'的十进制值相同。此外，题解中已经通过记录第一个0来处理所有以0开始的子字符串异或的情况，因为0异或任何数等于那个数本身。因此，算法优化通过跳过这些无关紧要的0，直接从第一个1开始计算，以提高效率和减少不必要的计算。

题解中提到的这一点是准确的。在二进制异或运算中，0异或任何数确实得到该数本身。因此，若查询中出现0，其结果直接为查询的另一部分数值，无需进一步计算。题解中只记录第一个0的位置是基于优化考虑，因为任何以0为起始的子字符串，其异或结果均为查询的另一部分数值，无需重复记录或计算。这样做可以简化数据结构并加快查询速度。

题解中选择30位作为子字符串的最大长度是基于二进制表示的整数范围考虑。在计算机中，一个常用的整数表示范围是32位整数，其中30位足以覆盖从0到2^30-1的所有整数，这个范围包括大约10亿个数值。对于大多数实际应用和算法竞赛，这个长度已经足够用来处理大部分情况。此外，设置一个合理的长度上限可以防止在极端情况下算法性能下降，例如避免在一个很长的全'1'字符串中进行不必要的计算。