मान लीजिए हमारे पास दो स्ट्रिंग्स 'a' और 'b' और एक स्ट्रिंग 'merge' है। कार्य स्ट्रिंग 'merge' को 'a' और 'b' के कैरेक्टर्स से इस तरह भरना है कि,
- यदि स्ट्रिंग 'a' नॉन-खाली है, तो स्ट्रिंग 'a' से पहला कैरेक्टर हटाएं और इसे स्ट्रिंग 'merge' में कॉपी करें।
- यदि स्ट्रिंग 'b' नॉन-खाली है, तो स्ट्रिंग 'b' से पहला कैरेक्टर हटाएं और इसे स्ट्रिंग 'merge' में कॉपी करें।
- यदि स्ट्रिंग्स 'a' और 'b' नॉन-खाली हैं, तो स्ट्रिंग 'a' से पहला कैरेक्टर हटाएं और इसे स्ट्रिंग 'merge' में कॉपी करें और फिर स्ट्रिंग 'b' से पहला कैरेक्टर (यदि कोई हो) हटाएं और इसे स्ट्रिंग 'merge' में कॉपी करें।
- दोनों स्ट्रिंग्स से कैरेक्टर्स को लेक्सिकोग्राफिकली हटाएं, जिसका अर्थ है, यदि स्ट्रिंग 'a' स्ट्रिंग 'b' से बड़ी है, तो स्ट्रिंग 'a' से कैरेक्टर हटाएं और फिर स्ट्रिंग 'b' से।
- स्ट्रिंग 'merge' लौटाएं।
उदाहरण के लिए
इनपुट-1:
a = "bacaa" b = "abcaa"
आउटपुट:
babcacaaaa
व्याख्या:
चूंकि दी गई स्ट्रिंग 'a' स्ट्रिंग 'b' से लेक्सिकोग्राफिकली बड़ी है, हम स्ट्रिंग 'a' से पहला कैरेक्टर निकालेंगे, यानी "b" और फिर स्ट्रिंग 'b' से। निकालने के बाद, स्ट्रिंग "babcacaaaa" बन जाएगी।
इस समस्या को हल करने का दृष्टिकोण
इस समस्या को हल करने का रिकर्सिव दृष्टिकोण यह है कि हम स्ट्रिंग 'a' और स्ट्रिंग 'b' के प्रत्येक कैरेक्टर को निकालेंगे और जांचेंगे कि क्या स्ट्रिंग 'a' के कैरेक्टर दूसरी स्ट्रिंग से लेक्सिकोग्राफिकली बड़े हैं और अंत में स्ट्रिंग 'merge' के साथ जोड़ देंगे।
हम कुछ पोजीशन के बाद प्रत्येक कैरेक्टर का सबस्ट्रिंग ढूंढेंगे और यदि यह दूसरी स्ट्रिंग से लेक्सिकोग्राफिकली बड़ा है तो 'merge' में जोड़ देंगे।
- दो इनपुट स्ट्रिंग्स 'a' और 'b' लें।
- एक रिकर्सिव स्ट्रिंग फ़ंक्शन concatenateLargest(string a, string b) दो स्ट्रिंग्स को इनपुट के रूप में लेता है और कन्कटनेशन के बाद सबसे बड़ी स्ट्रिंग लौटाता है, यानी (स्ट्रिंग 'a' + स्ट्रिंग 'b')।
- यदि दोनों स्ट्रिंग्स खाली हैं, तो स्ट्रिंग 'a' + स्ट्रिंग 'b' लौटाएं।
- यदि स्ट्रिंग 'a' स्ट्रिंग 'b' से कम या बराबर है, तो पहला कैरेक्टर निकालें और अन्य कैरेक्टर्स के लिए फ़ंक्शन को पुनरावर्ती रूप से कॉल करें।
- यदि स्ट्रिंग 'b' स्ट्रिंग 'b' से कम या बराबर है, तो पहला कैरेक्टर निकालें और अन्य कैरेक्टर्स के लिए फ़ंक्शन को पुनरावर्ती रूप से कॉल करें।
- कन्कटनेटेड स्ट्रिंग लौटाएं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
string concatenateLargest(string a, string b) {
if (a.size() == 0 or b.size() == 0) {
return (a + b);
}
if (a <= b)
return b[0] + concatenateLargest(a, b.substr(1));
else
return a[0] + concatenateLargest(a.substr(1), b);
}
int main() {
string a = "bacaa";
string b = "abcaa";
cout << concatenateLargest(a, b) << endl;
return 0;
}
उपरोक्त कोड चलाने से आउटपुट इस प्रकार उत्पन्न होगा,
आउटपुट
bacabcaaaa
दो स्ट्रिंग्स "bacaa" और "abcaa" दी गई समस्या के अनुसार मर्ज होने के बाद "bacabcaaaa" बन जाएंगी।