Trong hướng dẫn này, chúng ta cần giải quyết các truy vấn chuỗi con palindrome của chuỗi đã cho. Giải quyết các truy vấn chuỗi con palindrome phức tạp hơn nhiều so với việc giải quyết các truy vấn thông thường trong C ++. Nó yêu cầu mã và logic phức tạp hơn nhiều.
Trong hướng dẫn này, chúng tôi được cung cấp chuỗi str và số lượng Q của các truy vấn chuỗi con [L ... R], mỗi truy vấn có hai giá trị L và R. Chúng tôi nhằm mục đích viết một chương trình sẽ giải quyết các truy vấn để xác định xem có hay không chuỗi con [L. ..R] là một palindrome. Chúng ta phải quyết định xem chuỗi con được tạo thành trong phạm vi từ L đến R có phải là một palindrome hay không để giải quyết từng truy vấn. Ví dụ -
Let's input "abbbabaaaba" as our input string. The queries were [3, 13], [3, 11], [5, 8], [8, 12] It is necessary to determine whether the substring is a plaindrome A palindrome is "abaaabaaaba" (3, 13) . It is not possible to write "baaa" as a palindrome [3, 11]. As in [5, 8]: "aaab" cannot be a palindrome. There is a palindrome in "baaab" ([3, 12]).
Phương pháp tiếp cận để tìm giải pháp
Phương pháp ngây thơ
Ở đây, chúng ta phải tìm một palindrome bằng cách kiểm tra xem chuỗi con có nằm trong phạm vi chỉ mục L đến R. Do đó, chúng ta cần kiểm tra lần lượt tất cả các truy vấn chuỗi con và xác định xem chúng có phải là palindromes hay không. Vì có Q truy vấn và mỗi truy vấn mất 0 (N) thời gian để trả lời. Phải mất 0 (Q.N) thời gian trong trường hợp xấu nhất.
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] = {{3, 5}, {5, 7}, {2, 1}};
solveAllQueries(str, Q, query);
return 0;
} Đầu ra
Palindrome Palindrome Not palindrome!
Phương pháp lập trình động
Sử dụng phương pháp lập trình động để giải quyết vấn đề là một lựa chọn hiệu quả. Để giải quyết, chúng ta sẽ cần tạo một mảng DP, là một mảng hai chiều chứa giá trị boolean cho biết chuỗi con [i ... j] có phải là palindrome cho DP [i] [j] hay không.
Ma trận DP này sẽ được tạo và tất cả các giá trị L-R cho mỗi truy vấn sẽ được kiểm tra.
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] = {{3, 5}, {5, 7}, {2, 1}};
solveAllQueries(str, Q, query);
return 0;
} Đầu ra
palindrome! not palindrome! palindrome!
Kết luận
Trong hướng dẫn này, chúng tôi đã học cách giải quyết các truy vấn chuỗi con palindrome cùng với mã c ++. Chúng tôi cũng có thể viết mã này bằng java, python và các ngôn ngữ khác. Mã này là một trong những mã phức tạp và dài dòng nhất. Các truy vấn Palindrome khó hơn các truy vấn chuỗi con thông thường và chúng yêu cầu logic rất chính xác. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.