构建回文串检测
题面
leetcode题目
给你一个字符串 \(s\)，请你对 \(s\) 的子串进行检测。
每次检测，待检子串都可以表示为 \(queries[i] = [left, right, k]\)。我们可以 重新排列 子串 \(s[left], \cdots, s[right]\)，并从中选择 最多 \(k\) 项替换成任何小写英文字母。
如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为 true，否则结果为 false。
返回答案数组 \(answer[]\)，其中 \(answer[i]\) 是第 i 个待检子串 \(queries[i]\) 的检测结果。
注意：在替换时，子串中的每个字母都必须作为 独立的 项进行计数，也就是说，如果 \(s[left\cdots right] = aaa\) 且\(k = 2\)，我们只能替换其中的两个字母。（另外，任何检测都不会修改原始字符串 \(s\)，可以认为每次检测都是独立的）
example
输入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出：[true,false,false,true,true]
解释：
queries[0] : 子串 = "d"，回文。
queries[1] : 子串 = "bc"，不是回文。
queries[2] : 子串 = "abcd"，只替换 1 个字符是变不成回文串的。
queries[3] : 子串 = "abcd"，可以变成回文的 "abba"。 也可以变成 "baab"，先重新排序变成 "bacd"，然后把 "cd" 替换为 "ab"。
queries[4] : 子串 = "abcda"，可以变成回文的 "abcba"。
提示
- \(1 <= s.length, queries.length <= 10^5\)
- \(0 <= queries[i][0] <= queries[i][1] < s.length\)
- \(0 <= queries[i][2] <= s.length\)
- \(s\) 中只有小写英文字母
题解
总体思路
因为对串的改造是不会影响原串的，比较容易的我们可以考虑对原始字符串进行预处理，来降低处理的时间。
我们这样考虑回文串，如果一个串是回文串，那么一定满足:
- 如果串长度为奇数，那么有且只有一个元素是非成对出现的。
- 如果串长度是偶数，那么所有出现的元素一定都是成对出现的。
我们再进一步考虑，串\(s\)如果能对其元素做重新排列，那么当满足:
- 所有出现的元素都是成对出现的。
- 有且仅有一个元素是非成对出现的。 这两种情况时，则可以重排列为回文串。
更进一步的，如果串不满足上述条件，但可以对其中的元素进行修改，很容易可以想到按以下方式进行修改是最优的:
- 如果元素成对出现，不需要进行修改，只需要对称的排列即可。
- 如果元素没有成对出现，那么将两个落单的元素摆在对称位置，且只需要修改其中一个的值为另一个的值即可。
- 修改后如果有且仅有一个落单的元素，那么只需要摆到对称轴上即可。
于是思路就很清晰啦，按照上述原则进行修改，计算需要修改的次数\(cnt\)，和查询的值\(k\)进行比较就可以的得到结果。
显然的，由于对串的查询不会修改串本身，我们对串进行预处理，维护\(count\)数组其中\(count[i][j]\)元素表示第\(i\)位置向左的所有\(j\)元素的个数。
那么\(count[right][c] - count[left-1][c]\)就可以表示出\(s[i\cdots j]\)中间的所有元素\(c\)的个数，对这一值的查询就优化到\(O(1)\)。
由于串比较长，最长有\(10^5\)。我们不去遍历子串本身，只需要遍历26个字母即可，这样单次查询的时间复杂的也就维持到了 \(O(26)\)， 整体的时间复杂度则为\(O(s.length \times 26) + O(queries.length \times 26)\),即可表示为\(O(s.length + queries.length)\)
代码
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| #include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <string>
#define _DEBUG
using namespace std;
class Solution
{
const int MAX = 26;
public:
int char2idx(char c)
{
if (c >= 'a' && c <= 'z')
{
return c - 'a';
}
else if (c >= 'A' && c <= 'Z')
{
return 26 + c - 'A';
}
return 0;
}
vector<bool> canMakePaliQueries(string s, vector<vector<int>> &queries)
{
vector<bool> ret;
int len = s.length();
int count[len + 1][MAX];
memset(count, 0, sizeof(int) * (len + 1) * MAX);
for (int i = 1; i <= len; i++)
{
int idx = char2idx(s[i - 1]);
for (int j = 0; j < MAX; j++)
{
count[i][j] = count[i - 1][j];
}
count[i][idx] = count[i - 1][idx] + 1;
}
for (auto iter = queries.begin(); iter != queries.end(); iter++)
{
vector<int> q = *iter;
int left = q[0] + 1;
int right = q[1] + 1;
int k = q[2];
#ifdef _DEBUG
cout << "left: " << left << " right: " << right << " k: " << k << endl;
#endif
int cnt = 0;
for (int i = 0; i < MAX; i++)
{
int diff = count[right][i] - count[left - 1][i];
if (diff % 2 == 1)
{
cnt++;
}
#ifdef _DEBUG
cout << "i: " << i << " count[right][i]:" << count[right][i] << " count[left - 1][i]:" << count[left - 1][i] << " diff:" << diff << endl;
#endif
}
int add1 = (cnt % 2 == 1);
cnt = cnt / 2;
int subLen = (right - left + 1);
int add2 = (subLen % 2 == 1);
#ifdef _DEBUG
cout << "cnt: " << cnt << " add1: " << add1 << " add2: " << add2 << endl;
#endif
if (cnt + add1 - add2 > k)
{
ret.push_back(false);
}
else
{
ret.push_back(true);
}
}
return ret;
}
};
int main()
{
Solution s;
string t = "qzcdmvmfinetotshixuto";
vector<vector<int>> q{{1, 5, 1}};
vector<bool> ret = s.canMakePaliQueries(t, q);
for (auto iter = ret.begin(); iter != ret.end(); iter++)
{
cout << *iter << " ";
}
cout << endl;
return 0;
}
|