在C ++程序中检查substring [L…R]是否为回文查询
在这个问题中，我们给字符串str和Q个查询数，每个查询由substring[L...R]的两个值L和R组成。我们的任务是创建一个程序来解决查询以检查substring[L…R]是否是回文。
问题描述-为了解决每个查询，我们需要检查在L到R范围内创建的子字符串是否是回文。
让我们举个例子来了解这个问题，
输入值
str = “abccbeba” , Q = 3
Query[][] = {{1, 4}, {0, 6}, {4, 6}}输出结果Palindrome Not Palindrome Palindrome
说明
Creating all substring for the given substrings : Substring[1...4] = “bccb”, it is a palindrome Substring[0...6] = “abccbeb”, it is a not palindrome Substring[4...6] = “beb”, it is a palindrome
解决方法
一个简单的解决方案是解决每个查询。为了解决这个问题，我们需要找到索引范围从L到R的子字符串。并检查该子字符串是否是回文。
该程序说明了我们解决方案的工作原理，
示例
#include <bits/stdc++.h>
using namespace std;
int isPallindrome(string str){
int i, length;
int flag = 0;
length = str.length();
for(i=0;i < length ;i++){
if(str[i] != str[length-i-1]) {
flag = 1; break;
}
}
if (flag==1)
return 1;
return 0;
}
void solveAllQueries(string str, int Q, int query[][2]){
for(int i = 0; i < Q; i++){ isPallindrome(str.substr(query[i][0] - 1, query[i][1] - 1))?cout<<"Palindrome\n":cout<<"Not palindrome!\n";
}
}
int main() {
string str = "abccbeba"; int Q = 3;
int query[Q][2] = {{1, 3}, {2, 5}, {4, 5}};
solveAllQueries(str, Q, query);
return 0;
}输出结果Palindrome Not palindrome! Palindrome
这是一种幼稚的方法，但不是有效的方法。
解决该问题的有效方法是使用动态编程方法。为了求解，我们需要创建一个DP数组，该数组是一个二维数组，该数组存储一个布尔值，该布尔值表示子字符串[i...j]是否是DP[i][j]的回文。
我们将创建此DP矩阵，并检查每个查询的所有LR值。
该程序说明了我们解决方案的工作原理，
示例
#include <bits/stdc++.h>
using namespace std;
void computeDP(int DP[][50], string str){
int length = str.size();
int i, j;
for (i = 0; i < length; i++) {
for (j = 0; j < length; j++)
DP[i][j] = 0;
}
for (j = 1; j <= length; j++) {
for (i = 0; i <= length - j; i++) {
if (j <= 2) {
if (str[i] == str[i + j - 1])
DP[i][i + j - 1] = 1;
}
else if (str[i] == str[i + j - 1])
DP[i][i + j - 1] = DP[i + 1][i + j - 2];
}
}
}
void solveAllQueries(string str, int Q, int query[][2]){
int DP[50][50];
computeDP(DP, str);
for(int i = 0; i < Q; i++){
DP[query[i][0] - 1][query[i][1] - 1]?cout<<"not palindrome!\n":cout<<"palindrome!\n";
}
}
int main() {
string str = "abccbeba"; int Q = 3;
int query[Q][2] = {{1, 3}, {2, 5}, {4, 5}};
solveAllQueries(str, Q, query);
return 0;
}输出结果palindrome! not palindrome! palindrome!