LC-6356.子字符串异或查询

题目描述

leetcode 中等题

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

提示1：

1 <= s.length <= 10^4
s[i] 要么是 '0' ，要么是 '1' 。
1 <= queries.length <= 10^5
0 <= firsti, secondi <= 10^9

预处理

题目 $val \oplus first = second$ 可以转化成 $val = first \oplus second$，此时我们对每个询问可以直接计算出对应的 $val$ ，再判断该 $val$ 是否为原字符串的一个子串即可。

但是注意到 $queries.length <= 10^5, s.length <= 10 ^4$ ，也就是说就算使用 KMP 算法 $O(n + m)$ 的判断子串也会超时。

一个关键的部分是 $0 <= firsti, secondi <= 10^9$ ，所以他们的异或结果的二进制表示不会超过 $30$ 位，那么我们就可以预处理出原字符串所有小于等于 $30$ 长度的子串及其对应下标的映射关系，后面的询问过程就只需直接查询结果即可，此时时间复杂度为 $O(30N + M)$ 。

class Solution {
    public int[][] substringXorQueries(String s, int[][] queries) {
        int n = s.length();
        int m = queries.length;
        Map<String, int[]> memo = new HashMap<>();
        for(int i = 0; i < n; i++){
            StringBuilder sb = new StringBuilder();
            for(int j = i; j <= i + 30 && j < n; j++){
                sb.append(s.charAt(j));
                memo.putIfAbsent(sb.toString(), new int[]{i, j});
            }
        }
        int[][] ans = new int[m][2];
        int[] noExist = new int[]{-1, -1};
        for(int i = 0; i < m; i++){
            String cur = Integer.toBinaryString(queries[i][0] ^ queries[i][1]);
            ans[i] = memo.getOrDefault(cur, noExist);
        }
        return ans;
    }
}