Một chuỗi được cho là chuỗi palindromic nếu nó vẫn giữ nguyên sau khi đảo ngược nó.
Trong bài toán cụ thể này, chúng tôi đã đưa ra hai chuỗi 'a' và 'b' có cùng độ dài. Nếu chúng được phân tách với một số chỉ mục, thì nhiệm vụ là kiểm tra xem tổng các chuỗi có tạo thành palindrome hay không.
Giả sử chúng ta có hai chuỗi 'a' và 'b' có độ dài '4' và sau khi tách cả hai chuỗi ở chỉ mục '3' sao cho,
aaa | b và bbb | a
aaa (tiền tố của chuỗi đầu tiên) + a (hậu tố của chuỗi thứ hai) phải là Palindrome
HOẶC
b (hậu tố của chuỗi đầu tiên) + bbb (tiền tố của chuỗi thứ hai) phải là Palindrome
Ví dụ
Đầu vào-1:
a = “abcdef”b = “fedcba”
Đầu ra:
True
Giải thích: Sau khi tách Chuỗi 'a' và Chuỗi 'b' tại chỉ mục '2', chúng sẽ trở thành,
abc | def và feed | cba
Như vậy abc (tiền tố của chuỗi đầu tiên) + cba (hậu tố của chuỗi thứ hai) tạo thành một chuỗi palindromic. Do đó, chúng tôi sẽ trả về "True".
Đầu vào-2:
a = “eatable”b = “tableau”
Đầu ra:
False
Giải thích: Không có cách nào khả thi để biến hai chuỗi này thành palindrome.
Phương pháp tiếp cận để giải quyết vấn đề này
Để giải quyết vấn đề cụ thể này, chúng tôi sẽ sử dụng phương pháp tiếp cận hai con trỏ. Trong cách tiếp cận này, trước tiên, chúng tôi sẽ khởi tạo hai con trỏ, thấp và cao, sao cho điểm thấp đến '0' và điểm cao cho ký tự cuối cùng của chuỗi.
Vì độ dài của cả hai chuỗi bằng nhau, chúng tôi sẽ kiểm tra xem có chuỗi nào có ít hơn 2 ký tự hay không. Nếu có, chúng tôi sẽ trả về True. Nếu không, chúng tôi sẽ kiểm tra đệ quy bằng cách lặp qua toàn bộ chuỗi với sự trợ giúp của con trỏ. Nếu cả hai chuỗi đều bằng nhau thì trả về True, ngược lại là False.
- Lấy hai chuỗi tương ứng là 'a' và 'b'.
- Kiểm tra hàm BooleanPalindromic (chuỗi a, chuỗi b) nhận hai chuỗi làm tham số đầu vào và trả về True hoặc False tương ứng.
- Khởi tạo hai con trỏ, thấp và cao, với low =0 và high =độ dài của chuỗi 'b'.
- Lặp lại chuỗi và kiểm tra xem các ký tự của cả hai chuỗi có bằng nhau hay không.
- Một phép tách hàm Boolean (chuỗi a, chuỗi b) nhận hai chuỗi và trả về True nếu chúng là palindrome, nếu không thì False.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string a, int low, int high) {
while (low < high) {
if (a[low] != a[high])
return false;
low++;
high--;
}
return true;
}
bool Split(string a, string b) {
int low = 0;
int high = b.size() - 1;
while (low < high and a[low] == b[high]) {
low++;
high--;
}
return isPalindrome(a, low, high) || isPalindrome(b, low, high);
}
bool checkPalindromic(string a, string b) {
if (a.size() < 2)
return true;
return Split(a, b) || Split(b, a);
}
int main() {
string a = "abcpqr";
string b = "mnocba";
if (checkPalindromic(a, b)) {
cout << "True" << endl;
} else {
cout << "False" << endl;
}
return 0;
} Chạy đoạn mã trên sẽ tạo ra kết quả là,
Đầu ra
True
Giải thích: Nếu chúng ta chia các chuỗi đã cho 'abcpqr' và 'mnocba' tại chỉ mục '2' sao cho,
a (tiền tố) =abc và b (hậu tố) =cba
a (hậu tố) =pqr và b (tiền tố) =mno
Chúng ta có thể thấy rằng a (tiền tố) + b (hậu tố) tạo thành palindrome, do đó kết quả đầu ra là True.