একটি স্ট্রিংকে প্যালিনড্রোমিক স্ট্রিং বলা হয় যদি এটি বিপরীত করার পরে একই থাকে।
এই বিশেষ সমস্যায়, আমরা একই দৈর্ঘ্যের দুটি স্ট্রিং 'a' এবং 'b' দিয়েছি। যদি সেগুলিকে কিছু সূচী দিয়ে বিভক্ত করা হয়, তাহলে কাজ হল স্ট্রিংগুলির যোগফল একটি প্যালিনড্রোম তৈরি করে কিনা তা পরীক্ষা করা৷
ধরা যাক আমাদের কাছে '4' দৈর্ঘ্যের দুটি স্ট্রিং 'a' এবং 'b' আছে এবং সূচী '3'-এ উভয় স্ট্রিংকে বিভক্ত করার পরে,
আআ | b এবং bbb | a
aaa (প্রথম স্ট্রিংয়ের উপসর্গ) + a (দ্বিতীয় স্ট্রিংয়ের প্রত্যয়) প্যালিনড্রোম হওয়া উচিত
বা
b(প্রথম স্ট্রিং এর প্রত্যয়) + bbb(দ্বিতীয় স্ট্রিং এর উপসর্গ) হতে হবে প্যালিনড্রোম
উদাহরণস্বরূপ
ইনপুট-1:
a = “abcdef”b = “fedcba”
আউটপুট:
True
ব্যাখ্যা: '2' সূচকে স্ট্রিং 'a' এবং স্ট্রিং 'b' কে বিভক্ত করার পরে, তারা হয়ে যাবে,
abc | def এবং খাওয়ানো | সিবিএ
যেমন abc(প্রথম স্ট্রিংয়ের উপসর্গ) + cba(দ্বিতীয় স্ট্রিংয়ের প্রত্যয়) একটি প্যালিনড্রোমিক স্ট্রিং তৈরি করে। এইভাবে আমরা "সত্য" ফিরে আসব।
ইনপুট-2:
a = “eatable”b = “tableau”
আউটপুট:
False
ব্যাখ্যা: এই দুটি স্ট্রিং প্যালিনড্রোম করার কোন সম্ভাব্য উপায় নেই।
এই সমস্যা সমাধানের পদ্ধতি
এই বিশেষ সমস্যা সমাধানের জন্য, আমরা দুই-পয়েন্টার পদ্ধতি ব্যবহার করব। এই পদ্ধতিতে, প্রথমে, আমরা দুটি পয়েন্টার শুরু করব, নিম্ন এবং উচ্চ, যেমন নিম্ন বিন্দু '0' এবং উচ্চ বিন্দু স্ট্রিংটির শেষ অক্ষর।
যেহেতু উভয় স্ট্রিং এর দৈর্ঘ্য সমান, আমরা পরীক্ষা করব যে তাদের মধ্যে 2টির কম অক্ষর আছে কিনা। যদি হ্যাঁ, আমরা সত্য ফিরে আসব. অন্যথায়, আমরা পয়েন্টারগুলির সাহায্যে পুরো স্ট্রিংটি পুনরাবৃত্তি করে পুনরাবৃত্তি করে পরীক্ষা করব। উভয় স্ট্রিং সমান হলে, সত্য, অন্যথায় মিথ্যা ফেরত দিন।
- দুটি স্ট্রিং নিন, যথাক্রমে 'a' এবং 'b'।
- একটি বুলিয়ান ফাংশন চেকপ্যালিনড্রোমিক (স্ট্রিং a, স্ট্রিং b) ইনপুট প্যারামিটার হিসাবে দুটি স্ট্রিং নেয় এবং সেই অনুযায়ী সত্য বা মিথ্যা প্রদান করে।
- নিম্ন এবং উচ্চ, নিম্ন =0 এবং উচ্চ =স্ট্রিং 'b' এর দৈর্ঘ্য সহ দুটি পয়েন্টার শুরু করুন।
- স্ট্রিংটির উপরে পুনরাবৃত্তি করুন এবং উভয় স্ট্রিংয়ের অক্ষর সমান কিনা তা পরীক্ষা করুন।
- একটি বুলিয়ান ফাংশন বিভক্ত (স্ট্রিং a, স্ট্রিং b) দুটি স্ট্রিং নেয় এবং যদি সেগুলি প্যালিনড্রোম হয় True, অন্যথায় False হয়৷
উদাহরণ
#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(উপসর্গ) =abc এবং b(প্রত্যয়) =cba
a(প্রত্যয়) =pqr এবং b(prefix) =mno
আমরা লক্ষ্য করতে পারি যে a(উপসর্গ) + b(প্রত্যয়) একটি প্যালিনড্রোম তৈরি করে, তাই আউটপুটটি সত্য।
