You are given a binary string s
, and a 2D integer array queries
where queries[i] = [firsti, secondi]
.
For the ith
query, find the shortest substring of s
whose decimal value, val
, yields secondi
when bitwise XORed with firsti
. In other words, val ^ firsti == secondi
.
The answer to the ith
query is the endpoints (0-indexed) of the substring [lefti, righti]
or [-1, -1]
if no such substring exists. If there are multiple answers, choose the one with the minimum lefti
.
Return an array ans
where ans[i] = [lefti, righti]
is the answer to the ith
query.
A substring is a contiguous non-empty sequence of characters within a string.
Example 1:
Input: s = "101101", queries = [[0,5],[1,2]] Output: [[0,2],[2,3]] Explanation: For the first query the substring in range[0,2]
is "101" which has a decimal value of5
, and5 ^ 0 = 5
, hence the answer to the first query is[0,2]
. In the second query, the substring in range[2,3]
is "11", and has a decimal value of 3, and 3^ 1 = 2
. So,[2,3]
is returned for the second query.
Example 2:
Input: s = "0101", queries = [[12,8]]
Output: [[-1,-1]]
Explanation: In this example there is no substring that answers the query, hence [-1,-1] is returned
.
Example 3:
Input: s = "1", queries = [[4,5]] Output: [[0,0]] Explanation: For this example, the substring in range[0,0]
has a decimal value of1
, and1 ^ 4 = 5
. So, the answer is[0,0]
.
Constraints:
1 <= s.length <= 104
s[i]
is either'0'
or'1'
.1 <= queries.length <= 105
0 <= firsti, secondi <= 109
Solution: Pre-compute
We can pre-compute all possible substrings
Time complexity: O(n*32 + m)
Space complexity: O(n*32)
C++
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 |
// Author: Huahua class Solution { public: vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& queries) { unordered_map<int, vector<int>> m; const int l = s.length(); for (int i = 0; i < l; ++i) { if (s[i] == '0') { if (!m.count(0)) m[0] = {i, i}; continue; } for (int j = 0, cur = 0; j < 32 && i + j < l; ++j) { cur = (cur << 1) | (s[i + j] - '0'); if (!m.count(cur)) m[cur] = {i, i + j}; } } vector<vector<int>> ans; for (const auto& q : queries) { int x = q[0] ^ q[1]; if (m.count(x)) ans.push_back(m[x]); else ans.push_back({-1, -1}); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment