Question

2564. 子字符串异或查询

English Version

题目描述

给你一个 二进制字符串 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

 

解法

方法一：预处理 + 枚举

我们可以先预处理出所有长度为 $1$ 到 $32$ 的子串对应的十进制值，找到每个值对应的最小下标以及对应的右端点下标，存放在哈希表 $d$ 中。

然后枚举每个查询，对于每个查询 $[first, second]$，我们只需要在哈希表 $d$ 中查找是否存在键为 $first \oplus second$ 的键值对，如果存在，把对应的最小下标和右端点下标加入答案数组即可，否则加入 $[-1, -1]$。

时间复杂度 $O(n \times \log M + m)$，空间复杂度 $O(n \times \log M)$。其中 $n$ 和 $m$ 分别为字符串 $s$ 和查询数组 $queries$ 的长度，而 $M$ 可以取整数的最大值 $2^{31} - 1$。

class Solution:
  def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:
    d = {}
    n = len(s)
    for i in range(n):
      x = 0
      for j in range(32):
        if i + j >= n:
          break
        x = x << 1 | int(s[i + j])
        if x not in d:
          d[x] = [i, i + j]
        if x == 0:
          break
    return [d.get(first ^ second, [-1, -1]) for first, second in queries]

class Solution {
  public int[][] substringXorQueries(String s, int[][] queries) {
    Map<Integer, int[]> d = new HashMap<>();
    int n = s.length();
    for (int i = 0; i < n; ++i) {
      int x = 0;
      for (int j = 0; j < 32 && i + j < n; ++j) {
        x = x << 1 | (s.charAt(i + j) - '0');
        d.putIfAbsent(x, new int[] {i, i + j});
        if (x == 0) {
          break;
        }
      }
    }
    int m = queries.length;
    int[][] ans = new int[m][2];
    for (int i = 0; i < m; ++i) {
      int first = queries[i][0], second = queries[i][1];
      int val = first ^ second;
      ans[i] = d.getOrDefault(val, new int[] {-1, -1});
    }
    return ans;
  }
}

class Solution {
public:
  vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& queries) {
    unordered_map<int, vector<int>> d;
    int n = s.size();
    for (int i = 0; i < n; ++i) {
      int x = 0;
      for (int j = 0; j < 32 && i + j < n; ++j) {
        x = x << 1 | (s[i + j] - '0');
        if (!d.count(x)) {
          d[x] = {i, i + j};
        }
        if (x == 0) {
          break;
        }
      }
    }
    vector<vector<int>> ans;
    for (auto& q : queries) {
      int first = q[0], second = q[1];
      int val = first ^ second;
      if (d.count(val)) {
        ans.emplace_back(d[val]);
      } else {
        ans.push_back({-1, -1});
      }
    }
    return ans;
  }
};

func substringXorQueries(s string, queries [][]int) (ans [][]int) {
  d := map[int][]int{}
  for i := range s {
    x := 0
    for j := 0; j < 32 && i+j < len(s); j++ {
      x = x<<1 | int(s[i+j]-'0')
      if _, ok := d[x]; !ok {
        d[x] = []int{i, i + j}
      }
      if x == 0 {
        break
      }
    }
  }
  for _, q := range queries {
    first, second := q[0], q[1]
    val := first ^ second
    if v, ok := d[val]; ok {
      ans = append(ans, v)
    } else {
      ans = append(ans, []int{-1, -1})
    }
  }
  return
}