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