สตริงจะเรียกว่าสตริงพาลินโดรมหากมันยังคงเหมือนเดิมหลังจากย้อนกลับ
ในปัญหาเฉพาะนี้ เราได้ให้สตริง 'a' และ 'b' สองสตริงที่มีความยาวเท่ากัน หากถูกแบ่งด้วยดัชนีบางรายการ ภารกิจคือตรวจสอบว่าผลรวมของสตริงสร้างพาลินโดรมหรือไม่
สมมติว่าเรามีสตริง 'a' และ 'b' สองสตริงที่มีความยาว '4' และหลังจากแยกสตริงทั้งสองที่ดัชนี '3' ออกแล้ว
aaa | ข และ bbb | ก
aaa (ส่วนนำหน้าของสตริงแรก) + a (ส่วนต่อท้ายของสตริงที่สอง) ควรเป็น Palindrome
หรือ
b (คำต่อท้ายของสตริงแรก) + bbb (คำนำหน้าของสตริงที่สอง) ควรเป็น Palindrome
ตัวอย่าง
อินพุต-1:
a = “abcdef”b = “fedcba”
ผลลัพธ์:
True
คำอธิบาย: หลังจากแยกสตริง 'a' และสตริง 'b' ที่ดัชนี '2' แล้ว พวกมันจะกลายเป็น
abc | def และ fed | ซีบีเอ
เช่นนั้น abc (คำนำหน้าของสตริงแรก) + cba (ส่วนต่อท้ายของสตริงที่สอง) ทำให้สตริงพาลินโดรม ดังนั้นเราจะคืน "ความจริง" กลับคืนมา
อินพุต-2:
a = “eatable”b = “tableau”
ผลลัพธ์:
False
คำอธิบาย: ไม่มีทางเป็นไปได้ที่จะทำให้สองสายนี้ palindrome
แนวทางในการแก้ปัญหานี้
เพื่อแก้ปัญหานี้โดยเฉพาะ เราจะใช้วิธีการแบบสองตัวชี้ ในแนวทางนี้ อันดับแรก เราจะเริ่มต้นตัวชี้สองตัว คือ ต่ำและสูง โดยให้จุดต่ำเป็น '0' และจุดสูงไปยังอักขระตัวสุดท้ายของสตริง
เนื่องจากความยาวของสตริงทั้งสองเท่ากัน เราจะตรวจสอบว่ามีอักขระตัวใดตัวหนึ่งน้อยกว่า 2 ตัวหรือไม่ ถ้าใช่ เราจะคืนค่า True มิฉะนั้น เราจะตรวจสอบแบบเรียกซ้ำโดยวนซ้ำทั้งสตริงโดยใช้พอยน์เตอร์ หากสตริงทั้งสองเท่ากัน ให้คืนค่า True ไม่เช่นนั้นจะเป็นเท็จ
- ใช้สองสตริง 'a' และ 'b' ตามลำดับ
- ฟังก์ชันบูลีน checkPalindromic(สตริง a, สตริง b) รับสองสตริงเป็นพารามิเตอร์อินพุตและส่งกลับค่า True หรือ False ตามลำดับ
- เริ่มต้นตัวชี้สองตัว ต่ำและสูง โดยมีค่าต่ำ =0 และสูง =ความยาวของสตริง 'b'
- วนซ้ำบนสตริงและตรวจสอบว่าอักขระของทั้งสองสตริงเท่ากันหรือไม่
- การแยกฟังก์ชันบูลีน (สตริง a, สตริง b) รับสองสตริงและคืนค่า True หากเป็น palindrome มิฉะนั้นจะเป็นเท็จ
ตัวอย่าง
#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;
} การเรียกใช้โค้ดด้านบนจะสร้างผลลัพธ์เป็น
ผลลัพธ์
True
คำอธิบาย: หากเราแยกสตริงที่กำหนด 'abcpqr' และ 'mnocba' ที่ดัชนี '2' เช่นนั้น
a(prefix) =abc และ b(ต่อท้าย) =cba
a(suffix) =pqr และ b(prefix) =mno
เราสามารถสังเกตได้ว่า a(prefix) + b(suffix) สร้าง palindrome ดังนั้นผลลัพธ์จึงเป็น True
