数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学检查子串是否可以通过替换 K 个字符来构成回文串（针对 Q 个查询）
引言
在本教程中，我们将实现一种方法来检查子串是否可以通过替换 K 个字符来构成回文串（针对 Q 个查询）。回文串是指正读和反读都相同的单词。例如，“madam”、“refer”。
这里，Q 个查询是一个数值数组，包含起始索引、结束索引和 K 的值。输入字符串的起始和结束索引值用于选择位于这些起始和结束索引值之间的字符（两个值都包含在内）。
对于这种方法，考虑一个字符串 str，检查其子串是否可以通过替换 K 个字符来构成回文串。K 是为了使子串成为回文串而替换的字符数。
示例 1
String s = "abcdef"
Queries = {{1, 4, 2}, {0, 4, 2}}
输出
Yes Yes
解释
在上面的例子中，字符串是 "abcd"。
**查询 1** − [1, 4, 1]，起始索引为 1，结束索引为 4，最多可以替换的字符数最多为 2 个。范围 {1, 4} 内的子串是 "bcde"。
通过替换 1 个字符，它可以成为一个回文串，回文串是 "bcdd"。
**查询 2** − [0, 4, 3]，起始索引为 0，结束索引为 4，最多可以替换 2 个字符以使子串成为回文串。范围 {0, 4} 内的子串是 "abcde"。
是的，通过替换 2 个字符，它可以成为一个回文串，该回文串是 "abcba"。
示例 2
String s = "hello"
Queries = { { 1, 4, 0 }, {1, 4, 2 }, { 7, 10, 3 }};
输出
No Yes Yes
解释
输入字符串是 "helloindia"
**查询 − {1, 4, 0}** − 起始索引为 1，结束索引为 4，最多可以替换 0 个字符以使子串成为回文串。范围 {1, 4} 内的子串是 "ello"。
否，通过替换 0 个字符，它不能成为回文串。
**查询 − {1, 4, 2}** − 起始索引为 1，结束索引为 4，最多可以替换 2 个字符以使子串成为回文串。范围 {1, 4} 内的子串是 "ello"。
是的，通过替换 2 个字符，它可以成为一个回文串。替换 2 个字符后的回文串是 "elle"。
**查询 − {7, 10, 3}** − 起始索引为 7，结束索引为 10，最多可以替换 3 个字符以使子串成为回文串。范围 {7, 10} 内的子串是 "india"。
是的，它可以通过替换字符来构成回文串。替换 2 个字符后的回文串是 "indni"。
语法
**length()** − 这是在 `
` 头文件中定义的字符串类库函数。它返回字符串的长度。字符串的长度是字符串的字符数。
string_name.length();
**vector** − 它是 C++ 中用于存储元素的容器。它是一个动态数组，不受数组大小限制。它可以是不同数据类型。
vector<data_type> vector_name;
**vector
vector<vector<data_type> > vector_name;
算法
初始化字符串 s。
使用数值数组初始化查询。
使用循环迭代字符串字符。
创建一个二维向量，用于存储使用查询的起始和结束索引值生成的子串。
使用子串处理查询并计算不匹配的字符数。
将一半的不匹配字符与剩余字符转换。
如果更改的字符数等于或小于 k 的值，则输出为“Yes”。
如果替换的字符数大于 K 的值，则输出“No”。
处理所有查询。
示例 1
我们使用 C++ 中的动态规划实现了其中一个演示。动态规划降低了时间复杂度，并且不会多次执行相同的步骤。它将任务分成多个部分并使用递归。
#include <bits/stdc++.h>
using namespace std;
//User-defined function to find the palindromic strings from the generated substring
void findPalindrome(string s, vector<vector<int> >& Q){
int l = s.length();
vector<vector<int> > dpa(26, vector<int>(l, 0)); // 2d array to store the character count
//iterating the string to generate the substring
for (int x = 0; x < 26; x++) {
char currentCharVal= x + 'a'; // value of current character
for (int y = 0; y < l; y++) {
// Updating the dp array with new values of counter characters
if (y == 0) {
dpa[x][y] = (s[y] == currentCharVal); }
else {
dpa[x][y] = dpa[x][y - 1] + (s[y] == currentCharVal);
}
}
}
// Processing queries
for (auto query : Q) {
int leftInd = query[0];
int rightInd = query[1];
int k = query[2];
int unMatched = 0; // Find and storing the unmatched characters
for (int x = 0; x < 26; x++){
int cnt = dpa[x][rightInd] - dpa[x][leftInd] + (s[leftInd] == (x + 'a'));
if (cnt & 1)
unMatched++;
}
int result = unMatched / 2; // Initializing the value of result variable
// defining the condition for the Output
if (result <= k) {cout << "YES\n"; }
else {cout << "NO\n"; }
}
}
int main() {
string s = "helloindia";
vector<vector<int> > Q; // Initializing queries
Q = { { 1, 4, 0 }, {1, 4, 2 }, { 6, 9, 2 }, { 3, 8, 4 }};
// calling the function for processing the queries and generating substring
findPalindrome(s, Q);
return 0;
}
输出
NO YES YES YES
示例 2
我们可以在本教程中无需动态规划即可实现问题陈述。对于生成子串和处理查询，使用了循环。使用变量“changes”计算已更改的字符数。当更改计数小于或等于 K 时，输出为“Yes”，否则输出为“No”。
使用 auto 自动定义变量的数据类型。
#include <iostream>
#include <vector>
using namespace std;
// Function to generate the substring and process the queries to check substring can be palindrome or not
void checkPalindrome(string s, vector<vector<int>>& Q) {
//processing queries
for (auto query : Q) {
int leftVal = query[0];
int rightVal = query[1];
int k = query[2];
int l = rightVal - leftVal + 1;
int unmatchedCnt = 0;
//vector to store values of characters
vector<int> cnt(26, 0);
//generating substring
for (int x = leftVal; x <= rightVal; x++)
cnt[s[x] - 'a']++;
for (int x = 0; x < 26; x++) {
if (cnt[x] % 2 != 0)
unmatchedCnt++;
}
int changes = unmatchedCnt / 2;
// condition for the Output
if (changes <= k)
cout << "YES\n";
else{
cout << "NO\n";
}
}
}
//Code Controller
int main() {
string s = "helloindia";
vector<vector<int>> Q = { { 1, 4, 0 }, {1, 4, 2 }, { 6, 9, 2 }, { 3, 8, 4 }};
checkPalindrome(s, Q);
return 0;
}
输出
NO YES YES YES
结论
我们已经完成了本教程。在本教程中，我们考虑一个字符串，并通过查询生成子串。我们检查子串是否可以通过替换最多 K 个字符来构成回文串。K 是将子串转换为回文串而替换的最大字符数。为了在 C++ 中实现该任务，我们使用了循环和动态规划。在本教程中，我们使用二维向量来存储查询。
163 次浏览
