2564-子字符串异或查询

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

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

本题 视频讲解 已出炉，欢迎一键三连！

把等式 val} \oplus \textit{first} = \textit{second 两边同时异或 first，得到

\textit{val} \oplus \textit{first} \oplus \textit{first} = \textit{second} \oplus \textit{first}

由于 first} \oplus \textit{first} = 0，因此上式化简为

\textit{val} = \textit{second}\oplus \textit{first}

所以问题等价于在 s 中找到值为 second}\oplus \textit{first 的数。

由于 10^9<2^{30，我们可以直接预计算所有 s 中长度不超过 30 的数及其对应的 left 和 right，记到一个哈希表中，然后 O(1) 地回答询问。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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]
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    private static final int[] NOT_FOUND = new int[]{-1, -1};

    public int[][] substringXorQueries(String S, int[][] queries) {
        var m = new HashMap<Integer, int[]>();
        int i = S.indexOf('0');
        if (i >= 0) m.put(0, new int[]{i, i}); // 这样下面就可以直接跳过 '0' 了，效率更高
        var s = S.toCharArray();
        for (int l = 0, n = s.length; l < n; ++l) {
            if (s[l] == '0') continue;
            for (int r = l, x = 0; r < Math.min(l + 30, n); ++r) {
                x = x << 1 | (s[r] & 1);
                m.putIfAbsent(x, new int[]{l, r});
            }
        }

        var ans = new int[queries.length][];
        for (i = 0; i < queries.length; i++)
            ans[i] = m.getOrDefault(queries[i][0] ^ queries[i][1], NOT_FOUND);
        return ans;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> substringXorQueries(string s, vector<vector<int>> &queries) {
        unordered_map<int, pair<int, int>> m;
        if (auto i = s.find('0'); i != string::npos)
            m[0] = {i, i}; // 这样下面就可以直接跳过 '0' 了，效率更高
        for (int l = 0, n = s.length(); l < n; ++l) {
            if (s[l] == '0') continue;
            for (int r = l, x = 0; r < min(l + 30, n); ++r) {
                x = x << 1 | (s[r] & 1);
                if (!m.count(x)) m[x] = {l, r};
            }
        }

        vector<vector<int>> ans;
        for (auto &q : queries) {
            auto it = m.find(q[0] ^ q[1]);
            if (it == m.end()) ans.push_back({-1, -1});
            else ans.push_back({it->second.first, it->second.second});
        }
        return ans;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func substringXorQueries(s string, queries [][]int) [][]int {
	type pair struct{ l, r int }
	m := map[int]pair{}
	if i := strings.IndexByte(s, '0'); i >= 0 {
		m[0] = pair{i, i} // 这样下面就可以直接跳过 '0' 了，效率更高
	}
	for l, c := range s {
		if c == '0' {
			continue
		}
		for r, x := l, 0; r < l+30 && r < len(s); r++ {
			x = x<<1 | int(s[r]&1)
			if _, ok := m[x]; !ok {
				m[x] = pair{l, r}
			}
		}
	}

	ans := make([][]int, len(queries))
	notFound := []int{-1, -1} // 避免重复创建
	for i, q := range queries {
		p, ok := m[q[0]^q[1]]
		if !ok {
			ans[i] = notFound
		} else {
			ans[i] = []int{p.l, p.r}
		}
	}
	return ans
}

复杂度分析

  • 时间复杂度：O(n\log U + q)，其中 n 为 s 的长度，U=max(\textit{queries})，q 为 queries 的长度。
  • 空间复杂度：O(n\log U)。
 Comments
On this page
2564-子字符串异或查询
  1. 复杂度分析