"मैडम" या "रेसकार" दो ऐसे शब्द हैं, जो आगे की ओर एक ही तरह के बैकवर्ड को पढ़ते हैं, जिन्हें पैलिंड्रोम कहा जाता है।
यदि हमें स्ट्रिंग्स का एक संग्रह या सूची दी जाती है, तो हमें यह पता लगाने के लिए एक 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
कुशल या अनुकूलित दृष्टिकोण
हम इस समस्या को हल करने के लिए एक ट्राई डेटा संरचना का उपयोग कर सकते हैं।
सबसे पहले, हमें एक खाली ट्री बनानी होगी, और ऐरे में प्रत्येक स्ट्रिंग के लिए, हमें वर्तमान शब्द के रिवर्स को सम्मिलित करना होगा और यह भी स्टोर करना होगा कि यह किस इंडेक्स में पैलिंड्रोम है। फिर हमें सरणी को फिर से पार करना होगा, और प्रत्येक स्ट्रिंग के लिए, हमें निम्नलिखित करना होगा-
-
अगर यह ट्रू में उपलब्ध है, तो ट्रू रिटर्न करें
-
यदि यह आंशिक रूप से उपलब्ध है -- जाँच करें कि शेष शब्द पैलिंड्रोम है या नहीं यदि हाँ, तो सही लौटें जिसका अर्थ है कि एक जोड़ी पैलिंड्रोम बनाती है।
समय जटिलता: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
निष्कर्ष
इस ट्यूटोरियल में, हमने सीखा कि कैसे दो दृष्टिकोणों (ब्रूटफोर्स और ऑप्टिमाइज्ड) के साथ एक सरणी में पैलिंड्रोम जोड़ी को खोजना है। हम इस कोड को जावा, पायथन और अन्य भाषाओं में भी लिख सकते हैं। पहला दृष्टिकोण सभी दिए गए तत्वों को पार करके किसी भी समाधान को खोजने का एक बुनियादी तरीका है। इसके विपरीत, दूसरा दृष्टिकोण एक त्रिकोणीय डेटा संरचना का उपयोग करता है ताकि यह उत्तर दे सके कि लगभग रैखिक समय जटिलता है। हमें उम्मीद है कि आपको यह ट्यूटोरियल मददगार लगा होगा।