Leetcode-5175 Can Make Palindrome from Substring(构建回文串检测)

 1 #define _for(i,a,b) for(int i = (a);i < b;i ++)
 2 #define _rep(i,a,b) for(int i = (a);i > b;i --)
 3 
 4 class Solution
 5 {
 6     public:
 7         vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries)
 8         {
 9             vector<bool> v;
10             long long sum[100003][27];
11             memset(sum,0,sizeof(sum));
12             sum[1][s[0]-'a'] ++;
13             _for(i,2,s.size()+1)
14             {
15                 memcpy(sum[i],sum[i-1],sizeof(sum[i]));
16                 sum[i][s[i-1]-'a'] ++;
17             }
18             
19             _for(i,0,queries.size())
20             {
21                 int rnt = 0;
22                 _for(j,0,27)
23                 {
24                     int tmp = sum[queries[i][1]+1][j]-sum[queries[i][0]][j];
25                     if(tmp&0x1)
26                         rnt ++;
27                 }
28                 if(rnt/2<=queries[i][2])
29                     v.push_back(true);
30                 else
31                     v.push_back(false);
32             }
33             return v;
34         }
35 };