Trong bài toán này, chúng ta được cung cấp chuỗi str, số lượng truy vấn Q, mỗi truy vấn gồm hai giá trị L và R cho chuỗi con [L ... R]. Nhiệm vụ của chúng ta là tạo một chương trình giải các Truy vấn để kiểm tra xem chuỗi con [L… R] có phải là palindrome hay không.
Mô tả sự cố - Để giải quyết từng truy vấn, chúng ta cần kiểm tra xem chuỗi con được tạo trong phạm vi từ L đến R có phải là palindrome hay không.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
str = “abccbeba” , Q = 3
Query[][] = {{1, 4}, {0, 6}, {4, 6}} Đầu ra
Palindrome Not Palindrome Palindrome
Giải thích
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
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là giải quyết từng truy vấn. Để giải quyết nó, chúng ta cần tìm chuỗi con từ phạm vi chỉ mục L đến R. Và kiểm tra xem chuỗi con có phải là palindrome hay không.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
Palindrome Not palindrome! Palindrome
Đây là một cách tiếp cận ngây thơ nhưng không phải là một cách hiệu quả.
Một giải pháp hiệu quả cho vấn đề là sử dụng phương pháp lập trình động. Để giải quyết, chúng ta cần tạo một mảng DP, một mảng 2-D lưu trữ một giá trị boolean biểu thị liệu chuỗi con [i ... j] có phải là palindrome cho DP [i] [j] hay không.
Chúng tôi sẽ tạo ma trận DP này và kiểm tra tất cả các giá trị L-R của mỗi truy vấn.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
palindrome! not palindrome! palindrome!