2564.子字符串异或查询

链接：2564.子字符串异或查询
难度：Medium
标签：位运算、数组、哈希表、字符串
简介：请你返回一个数组 ans ，其中 ans[i] = [lefti, righti] 是第 i 个查询的答案。

题解 1 - rust

• 编辑时间：2023-02-12
• 执行用时：76ms
• 内存消耗：13.9MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn substring_xor_queries(s: String, queries: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        use std::collections::HashMap;
        let mut m = HashMap::<i32, (usize, usize)>::new();
        let s = s.chars().collect::<Vec<char>>();
        for i in 0..s.len() {
            let mut cur = 0;
            for j in i..s.len().min(i + 30) {
                cur = ((cur << 1) | (s[j] as usize - '0' as usize) as i32);
                if !m.contains_key(&cur) {
                    m.insert(cur, (i, j));
                } else {
                    let item = m.get_mut(&cur).unwrap();
                    if item.1 - item.0 + 1 > j - i + 1 {
                        item.0 = i;
                        item.1 = j
                    };
                }
            }
        }
        let mut ans: Vec<Vec<i32>> = vec![];
        for q in queries {
            let target = q[0] ^ q[1];
            let mut item = vec![-1i32; 2];
            if let Some((l, r)) = m.get(&target) {
                item[0] = *l as i32;
                item[1] = *r as i32;
            }
            ans.push(item);
        }
        ans
    }
}

题解 2 - cpp

• 编辑时间：2023-02-12
• 执行用时：356ms
• 内存消耗：116.2MB
• 编程语言：cpp
• 解法介绍：预处理。

class Solution {
public:
    typedef pair<int, int> pii;
    vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& queries) {
        unordered_map<int, pii> m;
        for (int i = 0; i < s.size(); i++) {
            int cur = 0;
            for (int j = i; j < min((int)s.size(), i + 30); j++) {
                cur = (cur << 1) | (s[j] - '0');
                if (!m.count(cur) || m[cur].second - m[cur].first + 1 > j - i + 1) m[cur] = make_pair(i, j); 
            }
        }
        vector<vector<int>> ans;
        for (auto &q : queries) {
            int target = q[0] ^ q[1];
            vector<int> item(2, -1);
            if (m.count(target)) item[0] = m[target].first, item[1] = m[target].second;
            ans.push_back(item);
        }
        return ans;
    }
};

题解 3 - typescript

• 编辑时间：2023-02-12
• 执行用时：2752ms
• 内存消耗：87.9MB
• 编程语言：typescript
• 解法介绍：暴力。

function substringXorQueries(s: string, queries: number[][]): number[][] {
  return queries
    .map(([v1, v2]) => (v1 ^ v2).toString(2))
    .map(item => {
      const i = s.indexOf(item);
      if (i == -1) return [-1, -1];
      return [i, i + item.length - 1];
    });
}

题解 4 - python

• 编辑时间：2023-02-12
• 执行用时：532ms
• 内存消耗：56.9MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:
        m = defaultdict()
        for i in range(len(s)):
            cur = 0
            for j in range(i, min(len(s), i + 30)):
                cur = (cur << 1) | (ord(s[j]) - ord('0'))
                if cur in m:
                    print(m[cur][1] - m[cur][0])
                if cur not in m or m[cur][1] - m[cur][0] >= j - i + 1:
                    m[cur] = (i, j)
        return [
            m.get(n1 ^ n2, (-1, -1))
            for n1, n2 in queries
        ]