Medium

题目描述

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

对于第 i 个查询，找到 s 的最短子字符串，其十进制值 val 与 firsti 进行按位异或运算后等于 secondi。换句话说，val ^ firsti == secondi。

第 i 个查询的答案是子字符串的端点（从 0 开始索引）[lefti, righti]，如果不存在这样的子字符串，则返回 [-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 <= 10^4
  • s[i] 是 ‘0’ 或 ‘1’
  • 1 <= queries.length <= 10^5
  • 0 <= firsti, secondi <= 10^9

提示：

  • 你不需要考虑长度大于 30 的子字符串。
  • 预处理所有长度不超过 30 的子字符串，并将最佳端点添加到字典中。

解题思路

这道题的关键在于理解异或运算的性质：如果 val ^ first = second，那么 val = first ^ second。因此对于每个查询 [first, second]，我们需要找到字符串 s 中表示十进制数 first ^ second 的最短子字符串。

核心思路：

  1. 预处理优化：由于 first 和 second 的范围是 [0, 10^9]，它们的异或结果最大不会超过 2^30，所以我们只需要考虑长度不超过 30 的子字符串。

  2. 哈希表存储：遍历字符串 s，对于每个位置 i，计算从该位置开始的所有可能子字符串（长度不超过 30）的十进制值，并将每个值与其最优区间端点存储在哈希表中。

  3. 最优选择：对于同一个十进制值，我们选择左端点最小的子字符串；如果左端点相同，选择长度最短的。

  4. 查询处理：对于每个查询 [first, second]，计算目标值 target = first ^ second，在哈希表中查找对应的区间端点。

特殊处理：

  • 需要特别注意以 ‘0’ 开头的子字符串，除了单独的 “0” 表示数字 0 外，其他以 ‘0’ 开头的子字符串在数值计算中会被忽略前导零。
  • 为了找到最短且左端点最小的子字符串，我们在遍历时优先记录更优的位置。

代码实现

class Solution {
public:
    vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& queries) {
        unordered_map<int, pair<int, int>> mp;
        int n = s.length();
        
        // 预处理所有长度不超过30的子字符串
        for (int i = 0; i < n; i++) {
            if (s[i] == '0') {
                // 处理单独的0
                if (mp.find(0) == mp.end()) {
                    mp[0] = {i, i};
                }
                continue;
            }
            
            int val = 0;
            for (int j = i; j < n && j - i + 1 <= 30; j++) {
                val = val * 2 + (s[j] - '0');
                if (mp.find(val) == mp.end()) {
                    mp[val] = {i, j};
                }
            }
        }
        
        vector<vector<int>> result;
        for (auto& query : queries) {
            int target = query[0] ^ query[1];
            if (mp.find(target) != mp.end()) {
                result.push_back({mp[target].first, mp[target].second});
            } else {
                result.push_back({-1, -1});
            }
        }
        
        return result;
    }
};

class Solution:
    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:
        mp = {}
        n = len(s)
        
        # 预处理所有长度不超过30的子字符串
        for i in range(n):
            if s[i] == '0':
                # 处理单独的0
                if 0 not in mp:
                    mp[0] = [i, i]
                continue
            
            val = 0
            for j in range(i, min(i + 30, n)):
                val = val * 2 + int(s[j])
                if val not in mp:
                    mp[val] = [i, j]
        
        result = []
        for first, second in queries:
            target = first ^ second
            if target in mp:
                result.append(mp[target])
            else:
                result.append([-1, -1])
        
        return result

public class Solution {
    public int[][] SubstringXorQueries(string s, int[][] queries) {
        var mp = new Dictionary<int, int[]>();
        int n = s.Length;
        
        // 预处理所有长度不超过30的子字符串
        for (int i = 0; i < n; i++) {
            if (s[i] == '0') {
                // 处理单独的0
                if (!mp.ContainsKey(0)) {
                    mp[0] = new int[] {i, i};
                }
                continue;
            }
            
            int val = 0;
            for (int j = i; j < n && j - i + 1 <= 30; j++) {
                val = val * 2 + (s[j] - '0');
                if (!mp.ContainsKey(val)) {
                    mp[val] = new int[] {i, j};
                }
            }
        }
        
        var result = new int[queries.Length][];
        for (int i = 0; i < queries.Length; i++) {
            int target = queries[i][0] ^ queries[i][1];
            if (mp.ContainsKey(target)) {
                result[i] = mp[target];
            } else {
                result[i] = new int[] {-1, -1};
            }
        }
        
        return result;
    }
}

var substringXorQueries = function(s, queries) {
    const mp = new Map();
    const n = s.length;
    
    // 预处理所有长度不超过30的子字符串
    for (let i = 0; i < n; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度数值
时间复杂度O(n × 30 + q) = O(n + q)
空间复杂度O(n × 30) = O(n)

其中 n 是字符串 s 的长度，q 是查询的数量。预处理阶段需要遍历所有可能的子字符串，每个位置最多扩展 30 位；查询阶段每个查询都是 O(1) 的哈希表查找。

相关题目