एक स्ट्रिंग को पैलिंड्रोमिक स्ट्रिंग कहा जाता है यदि यह उलटने के बाद भी वही रहती है।
इस विशेष समस्या में, हमने समान लंबाई के दो तार 'a' और 'b' दिए हैं। अगर उन्हें कुछ इंडेक्स के साथ विभाजित किया जाता है, तो कार्य यह जांचना है कि स्ट्रिंग्स का योग पैलिंड्रोम बनाता है या नहीं।
मान लें कि हमारे पास दो स्ट्रिंग 'ए' और 'बी' लंबाई '4' है और दोनों स्ट्रिंग को इंडेक्स '3' पर विभाजित करने के बाद,
आआ | ख और बीबीबी | ए
aaa (पहली स्ट्रिंग का उपसर्ग) + a (दूसरी स्ट्रिंग का प्रत्यय) पैलिंड्रोम होना चाहिए
या
b(पहली स्ट्रिंग का प्रत्यय) + bbb (दूसरी स्ट्रिंग का उपसर्ग) पालिंड्रोम होना चाहिए
उदाहरण के लिए
इनपुट-1:
a = “abcdef”b = “fedcba”
आउटपुट:
True
स्पष्टीकरण: स्ट्रिंग 'ए' और स्ट्रिंग 'बी' को इंडेक्स '2' पर विभाजित करने के बाद, वे बन जाएंगे,
एबीसी | डीईएफ़ और फेड | सीबीए
ऐसा कि abc (पहली स्ट्रिंग का उपसर्ग) + cba (दूसरी स्ट्रिंग का प्रत्यय) एक पैलिंड्रोमिक स्ट्रिंग बनाता है। इस प्रकार हम "सच" लौटाएंगे।
इनपुट-2:
a = “eatable”b = “tableau”
आउटपुट:
False
स्पष्टीकरण: इन दो तारों को पैलिंड्रोम बनाने का कोई संभावित तरीका नहीं है।
इस समस्या को हल करने का तरीका
इस विशेष समस्या को हल करने के लिए, हम दो-सूचक दृष्टिकोण का उपयोग करेंगे। इस दृष्टिकोण में, सबसे पहले, हम दो पॉइंटर्स, लो और हाई को इनिशियलाइज़ करेंगे, जैसे कि लो पॉइंट टू '0' और हाई पॉइंट्स टू लास्ट कैरेक्टर।
चूंकि दोनों तारों की लंबाई समान है, हम जांच करेंगे कि उनमें से किसी में 2 से कम वर्ण हैं या नहीं। यदि हां, तो हम ट्रू वापस आ जाएंगे। अन्यथा, हम पॉइंटर्स की मदद से पूरे स्ट्रिंग पर पुनरावृति करके पुनरावर्ती रूप से जाँच करेंगे। यदि दोनों तार बराबर हैं, तो सही है, अन्यथा गलत है।
- दो तार लें, क्रमशः 'ए' और 'बी'।
- एक बूलियन फ़ंक्शन checkPalindromic(string a, string b) इनपुट पैरामीटर के रूप में दो स्ट्रिंग लेता है और तदनुसार सही या गलत लौटाता है।
- दो पॉइंटर्स को इनिशियलाइज़ करें, लो और हाई, लो =0 और हाई =स्ट्रिंग 'बी' की लंबाई के साथ।
- स्ट्रिंग पर पुनरावृति करें और जांचें कि दोनों स्ट्रिंग्स के वर्ण समान हैं या नहीं।
- एक बूलियन फ़ंक्शन स्प्लिट (स्ट्रिंग ए, स्ट्रिंग बी) दो स्ट्रिंग लेता है और यदि वे पैलिंड्रोम हैं, तो सही है, अन्यथा गलत है।
उदाहरण
#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(उपसर्ग) =mno
हम देख सकते हैं कि a(prefix) + b(suffix) एक पैलिंड्रोम बनाता है, इसलिए आउटपुट ट्रू है।