"ম্যাডাম" বা "রেসকার" এমন দুটি শব্দ যা সামনের দিকের মতোই পশ্চাৎমুখী হয়, যাকে প্যালিনড্রোম বলে।
যদি আমাদের স্ট্রিংগুলির একটি সংগ্রহ বা তালিকা দেওয়া হয়, তাহলে আমাদের একটি C++ কোড লিখতে হবে যাতে এটি একটি প্যালিনড্রোম তৈরি করতে তালিকার যেকোনো দুটি স্ট্রিংকে একসাথে যোগ করতে পারে কি না। যদি প্রদত্ত তালিকায় এই ধরনের কোনো জোড়া স্ট্রিং বিদ্যমান থাকে, তাহলে আমাদের "হ্যাঁ" প্রিন্ট করতে হবে, অন্যথায় আমাদের "না" প্রিন্ট করতে হবে।
এই টিউটোরিয়ালে, ইনপুট হবে স্ট্রিংগুলির একটি অ্যারে, এবং আউটপুট সেই অনুযায়ী একটি স্ট্রিং মান হবে, উদাহরণস্বরূপ
ইনপুট
list[] = {"flat", "tea", "chair", "ptalf", "tea"} আউটপুট
Yes
একটি জোড়া "ফ্ল্যাট" এবং "পটালফ" আছে যা একটি প্যালিনড্রোম স্ট্রিং "ফ্ল্যাটপটালফ" গঠন করে।
ইনপুট
list[] = {"raman", "ram", "na", "ar", "man"} আউটপুট
Yes
একটি জোড়া "না" এবং "মানুষ" আছে যা একটি প্যালিনড্রোম স্ট্রিং "নমন" গঠন করে।
সমাধান খোঁজার পদ্ধতি
ব্রুট ফোর্স এপ্রোচ
অ্যারের প্রতিটি স্ট্রিংয়ের জন্য, অন্য সমস্ত স্ট্রিং পরীক্ষা করে দেখুন যে এটি অন্য কোনও স্ট্রিংয়ের সাথে প্যালিনড্রোম তৈরি করে কিনা। যদি এই ধরনের একটি জুড়ি পাওয়া যায়, সত্য ফিরে. যদি সমস্ত অ্যারের উপাদানগুলি এই ধরনের একটি জোড়া অনুসন্ধানের জন্য অতিক্রম করা হয়, এবং কোন উপযুক্ত জোড়া পাওয়া যায় না, তাহলে মিথ্যা ফেরত দিন৷
সময়ের জটিলতা:O(N^2)
স্থান জটিলতা:O(1)
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
bool isPalindrome (string str) {
int len = str.length ();
for (int i = 0; i < len / 2; i++)
if (str[i] != str[len - i - 1])
return false;
return true;
}
bool checkPalindromePair (vector < string > vect) {
for (int i = 0; i < vect.size () - 1; i++) {
for (int j = i + 1; j < vect.size (); j++) {
string check_str = "";
check_str = check_str + vect[i] + vect[j];
if (isPalindrome (check_str))
return true;
}
}
return false;
}
int main () {
vector < string > vect = { "flat", "tea", "chair", "ptalf", "tea"};
checkPalindromePair (vect) ? cout << "Yes" : cout << "No";
return 0;
} আউটপুট
Yes
দক্ষ বা অপ্টিমাইজড পদ্ধতি
এই সমস্যাটি সমাধান করার জন্য আমরা একটি ট্রাই ডেটা স্ট্রাকচার ব্যবহার করতে পারি।
প্রথমত, আমাদের একটি খালি ট্রাই তৈরি করতে হবে এবং অ্যারের প্রতিটি স্ট্রিংয়ের জন্য, আমাদের বর্তমান শব্দের বিপরীতটি সন্নিবেশ করতে হবে এবং এটি একটি প্যালিনড্রোম কোন সূচক পর্যন্ত সংরক্ষণ করতে হবে। তারপর আমাদের আবার অ্যারে অতিক্রম করতে হবে, এবং প্রতিটি স্ট্রিংয়ের জন্য, আমাদের নিম্নলিখিতগুলি করতে হবে-
-
যদি এটি True তে পাওয়া যায়, তাহলে true ফেরত দিন
-
যদি এটি আংশিকভাবে উপলব্ধ থাকে --বাকী শব্দটি প্যালিনড্রোম কিনা তা পরীক্ষা করে দেখুন যদি হ্যাঁ, তাহলে সত্যে ফিরে যান তার মানে একটি জোড়া একটি প্যালিনড্রোম গঠন করে৷
সময়ের জটিলতা:O(Nk^2)
স্থান জটিলতা:O(N)
যেখানে N হল তালিকার শব্দের সংখ্যা এবং k হল প্যালিনড্রোমের জন্য চেক করা সর্বোচ্চ দৈর্ঘ্য।
উদাহরণ 2
#include<bits/stdc++.h>
using namespace std;
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
#define ALPHABET_SIZE (26)
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')
struct TrieNode {
struct TrieNode *children[ALPHABET_SIZE];
vector < int >pos;
int id;
bool isLeaf;
};
struct TrieNode *
getNode (void) {
struct TrieNode *pNode = new TrieNode;
pNode->isLeaf = false;
for (int i = 0; i < ALPHABET_SIZE; i++)
pNode->children[i] = NULL;
return pNode;
}
bool isPalindrome (string str, int i, int len) {
while (i < len) {
if (str[i] != str[len])
return false;
i++, len--;
}
return true;
}
void insert (struct TrieNode *root, string key, int id) {
struct TrieNode *pCrawl = root;
for (int level = key.length () - 1; level >= 0; level--) {
int index = CHAR_TO_INDEX (key[level]);
if (!pCrawl->children[index])
pCrawl->children[index] = getNode ();
if (isPalindrome (key, 0, level))
(pCrawl->pos).push_back (id);
pCrawl = pCrawl->children[index];
}
pCrawl->id = id; pCrawl->pos.push_back (id);
pCrawl->isLeaf = true;
}
void
search (struct TrieNode *root, string key, int id,
vector < vector < int > >&result) {
struct TrieNode *pCrawl = root;
for (int level = 0; level < key.length (); level++) {
int index = CHAR_TO_INDEX (key[level]);
if (pCrawl->id >= 0 && pCrawl->id != id && isPalindrome (key, level, key.size () - 1)) result.push_back ( { id, pCrawl->id} );
if (!pCrawl->children[index]) return; pCrawl = pCrawl->children[index];
}
for (int i:pCrawl->pos) {
if (i == id) continue;
result.push_back ( { id, i} );
}
}
bool checkPalindromePair (vector < string > vect) {
struct TrieNode *root = getNode ();
for (int i = 0; i < vect.size (); i++)
insert (root, vect[i], i);
vector < vector < int >>result;
for (int i = 0; i < vect.size (); i++) {
search (root, vect[i], i, result);
if (result.size () > 0) return true;
}
return false;
}
// Driver code int main () {
vector < string > vect = { "flat", "tea", "chair", "ptalf", "tea"};
checkPalindromePair (vect) ? cout << "Yes" : cout << "No";
return 0;
} আউটপুট
Yes
উপসংহার
এই টিউটোরিয়ালে, আমরা শিখেছি কিভাবে দুটি পন্থা (ব্রুটফোর্স এবং অপ্টিমাইজড) সহ একটি অ্যারেতে একটি প্যালিনড্রোম জোড়া খুঁজে বের করতে হয়। আমরা জাভা, পাইথন এবং অন্যান্য ভাষায় এই কোডটি লিখতে পারি। প্রথম পন্থা হল প্রদত্ত সমস্ত উপাদান অতিক্রম করে যেকোনো সমাধান খুঁজে বের করার একটি মৌলিক উপায়। বিপরীতে, দ্বিতীয় পদ্ধতিটি একটি ট্রাই ডেটা কাঠামো ব্যবহার করে যাতে এটি উত্তর দেয় প্রায় রৈখিক সময় জটিলতা। আমরা আশা করি আপনার এই টিউটোরিয়ালটি সহায়ক হবে৷
