# 2564. Substring XOR Queries
###### tags: `Leetcode` `Medium` `Bit Manipulation`
Link: https://leetcode.com/problems/substring-xor-queries/description/
## 思路
把所有substring的decimal value算出来 并放在hashmap里
hashmap的value记录substring的起点和终点
乍看之下 时间复杂度是$O(n^2)$ 但由于这个decimal value一定是integer 所以substring的长度不超过31 因此时间复杂度是$O(31n)$
When we process queries, we look for the ```q[0]^q[1]``` value in the hashmap (since ```q[0]^q[0]^q[1] == q[1]```)
## Code

class Solution:
    def substringXorQueries(self, s: str, queries: List[List[int]]) -> List[List[int]]:
        n = len(s)
        seen = collections.defaultdict(lambda: [-1, -1])
        for i in range(n-1, -1, -1):
            if s[i]=='0':
                seen[0] = [i, i]
                continue
            val = 0
            for j in range(i, n):
                val = val*2+int(s[j])
                if val>2**32: break
                seen[val] = [i, j]
        return [seen[first^second] for first, second in queries]