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 trước. Giải quyết truy vấn chuỗi con palindrome phức tạp hơn nhiều so với giải quyết các truy vấn thông thường trong C++. Nó đòi hỏi code và logic phức tạp hơn nhiều.
Trong hướng dẫn này, chúng ta được cung cấp chuỗi str và Q số truy vấn chuỗi con[L...R], mỗi truy vấn có hai giá trị L và R. Mục tiêu của chúng ta là viết một chương trình sẽ giải quyết các Truy vấn để xác định xem chuỗi con[L...R] có phải là palindrome hay không. Chúng ta phải quyết định xem chuỗi con được hình thành trong phạm vi L đến R có phải là palindrome hay không để giải quyết mỗi truy vấn. Ví dụ:
Hãy nhập "abbbabaaaba" làm chuỗi đầu vào. Các truy vấn là [3, 13], [3, 11], [5, 8], [8, 12] Cần xác định xem chuỗi con có phải palindrome "abaaabaaaba" (3, 13) là palindrome. Không thể viết "baaa" thành palindrome [3, 11]. Như [5, 8]: "aaab" không thể là palindrome. Có palindrome trong "baaab" ([3, 12]).
Cách tiếp cận để tìm giải pháp
Phương pháp Naive
Ở đây, chúng ta phải tìm palindrome bằng cách kiểm tra xem chuỗi con có từ phạm vi chỉ số L đến R hay không. Do đó, chúng ta cần kiểm tra tất cả các truy vấn chuỗi con một bằng một và xác định xem chúng có phải palindrome 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. Nó 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 Quy hoạch động
Sử dụng cách tiếp cận quy hoạch động để giải quyết bài toá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, đây là một mảng hai chiều chứa giá trị boolean cho biết xem 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 ta đã học cách giải quyết truy vấn chuỗi con palindrome cùng với code C++. Chúng ta cũng có thể viết code này bằng Java, Python và các ngôn ngữ khác. Code này là một trong những code phức tạp và dài nhất. Truy vấn palindrome khó hơn truy vấn chuỗi con thông thường và chúng đòi hỏi logic rất chính xác. Hy vọng bạn thấy hướng dẫn này hữu ích.