"मैडम" या "रेसकार" दो ऐसे शब्द हैं जो पीछे से पढ़ने पर भी आगे की तरह ही पढ़े जाते हैं, इन्हें पैलिंड्रोम कहा जाता है।
यदि हमें स्ट्रिंग्स का एक संग्रह या सूची दी गई है, तो हमें यह पता लगाने के लिए C++ कोड लिखना होगा कि क्या उस सूची में किन्हीं दो स्ट्रिंग्स को जोड़कर पैलिंड्रोम बनाया जा सकता है या नहीं। यदि दी गई सूची में ऐसी कोई स्ट्रिंग जोड़ी मौजूद है, तो हमें "Yes" प्रिंट करना होगा, अन्यथा "No" प्रिंट करना होगा।
इस ट्यूटोरियल में, इनपुट स्ट्रिंग्स की एक सरणी होगी, और आउटपुट तदनुसार एक स्ट्रिंग मान होगा, उदाहरण के लिए
इनपुट
list[] = {"flat", "tea", "chair", "ptalf", "tea"}
आउटपुट
Yes
"flat" और "ptalf" की एक जोड़ी है जो पैलिंड्रोम स्ट्रिंग "flatptalf" बनाती है।
इनपुट
list[] = {"raman", "ram", "na", "ar", "man"}
आउटपुट
Yes
"na" और "man" की एक जोड़ी है जो पैलिंड्रोम स्ट्रिंग "naman" बनाती है।
समाधान खोजने का दृष्टिकोण
ब्रूट फोर्स दृष्टिकोण
सरणी में प्रत्येक स्ट्रिंग के लिए, जांचें कि क्या यह किसी अन्य स्ट्रिंग के साथ पैलिंड्रोम बनाती है या नहीं। यदि ऐसी जोड़ी मिलती है, तो true वापस करें। यदि ऐसी जोड़ी की खोज के लिए सभी सरणी तत्वों को पार किया जाता है, और कोई उपयुक्त जोड़ी नहीं मिलती है, तो false वापस करें।
समय जटिलता: O(N²)
स्पेस जटिलता: 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 वापस करें
यदि यह आंशिक रूप से उपलब्ध है -- शेष शब्द पैलिंड्रोम है या नहीं जांचें। यदि हां, तो true वापस करें जिसका अर्थ है कि एक जोड़ी पैलिंड्रोम बनाती है।
समय जटिलता: O(Nk²)
स्पेस जटिलता: 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
निष्कर्ष
इस ट्यूटोरियल में, हमने दो दृष्टिकोणों (ब्रूटफोर्स और अनुकूलित) के साथ एक सरणी में पैलिंड्रोम जोड़ी ढूंढना सीखा। हम इस कोड को जावा, पायथन और अन्य भाषाओं में भी लिख सकते हैं। पहला दृष्टिकोण सभी दिए गए तत्वों को पार करके किसी भी समाधान को खोजने का एक बुनियादी तरीका है। इसके विपरीत, दूसरा दृष्टिकोण ट्राई डेटा संरचना का उपयोग करता है ताकि यह लगभग रैखिक समय जटिलता में उत्तर दे सके। हमें उम्मीद है कि आपको यह ट्यूटोरियल उपयोगी लगा।
