मान लीजिए हमारे पास स्ट्रिंग्स की एक सूची है, हम इन स्ट्रिंग्स को एक लूप में संयोजित कर सकते हैं, जहां प्रत्येक स्ट्रिंग के लिए हम इसे उल्टा करना चुन सकते हैं या नहीं। सभी संभावित लूपों में से, हमें लूप को काटने के बाद शब्दकोश क्रम में सबसे बड़ी स्ट्रिंग ढूंढनी होगी, जो लूप्ड स्ट्रिंग को एक नियमित स्ट्रिंग में बदल देगा। विशेष रूप से, शब्दकोश क्रम में सबसे बड़ी स्ट्रिंग ढूंढने के लिए, हमें दो चरणों का अनुभव करना होगा:
दिए गए क्रम में सभी स्ट्रिंग्स को एक लूप में संयोजित करें, जहां हम कुछ स्ट्रिंग्स को उल्टा कर सकते हैं या नहीं।
लूप में किसी भी स्थान पर एक कटिंग बिंदु बनाएं, जो लूप्ड स्ट्रिंग को कटिंग बिंदु पर वर्ण से शुरू होने वाली एक नियमित स्ट्रिंग में बदल देगा। और काम सभी संभावित नियमित स्ट्रिंग्स में से शब्दकोश क्रम में सबसे बड़ी ढूंढना है।
उदाहरण के लिए, यदि इनपुट "abc", "xyz" है, तो आउटपुट "zyxcba" होगा क्योंकि हम लूप्ड स्ट्रिंग प्राप्त कर सकते हैं जैसे "-abcxyz-", "-abczyx-", "-cbaxyz-", "-cbazyx-"। उत्तर स्ट्रिंग चौथे लूप्ड से आई, जहां हम मध्य वर्ण 'a' से काट सकते हैं और "zyxcba" प्राप्त कर सकते हैं।
हल करने की विधि
हम निम्न चरणों का पालन करेंगे:
solve()फ़ंक्शन इंडेक्स, स्ट्रिंग्स सरणी, और रिवर्स फ्लैग लेता है।- वर्तमान स्ट्रिंग को लें, यदि रिवर्स है तो उल्टा करें।
- इससे पहले और बाद की सभी स्ट्रिंग्स को संयोजित करें।
- वर्तमान स्ट्रिंग के प्रत्येक संभावित कटिंग बिंदु के लिए, नई स्ट्रिंग बनाएं और अधिकतम अपडेट करें।
findMax()फ़ंक्शन प्रत्येक स्ट्रिंग को उसके उल्टे संस्करण के साथ तुलना करके अधिकतम संस्करण में बदलता है।- मुख्य विधि में: findMax कॉल करें, फिर प्रत्येक स्ट्रिंग के लिए solve को रिवर्स के साथ और बिना रिवर्स के कॉल करें।
- अधिकतम स्ट्रिंग लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; class Solution { public: string ret; void solve(int idx, vector <string > strs, bool rev){ string temp = strs[idx]; if (rev) reverse(temp.begin(), temp.end()); string str1 = ""; string str2 = ""; for (int i = 0; i < idx; i++) str1 += strs[i]; for (int i = idx + 1; i < strs.size(); i++) str2 += strs[i]; for (int k = 0; k < temp.size(); k++) { string newOne = temp.substr(k) + str2 + str1 + temp.substr(0, k); if (ret == "" || ret < newOne) { ret = newOne; } } } void findMax(vector<string>& strs){ for (int i = 0; i < strs.size(); i++) { string temp = strs[i]; reverse(temp.begin(), temp.end()); strs[i] = strs[i] > temp ? strs[i] : temp; } } string splitLoopedString(vector& strs) { ret = ""; findMax(strs); for (int i = 0; i < strs.size(); i++) { solve(i, strs, false); solve(i, strs, true); } return ret; } }; main(){ Solution ob; vector<string> v = {"abc", "xyz"}; cout << (ob.splitLoopedString(v)); }
इनपुट
{"abc", "xyz"}
आउटपुट
zyxcba
