सी ++ में विभाजित कॉनटेनेटेड स्ट्रिंग्स

मान लीजिए कि हमारे पास स्ट्रिंग्स की एक सूची है, हम इन स्ट्रिंग्स को एक लूप में एक साथ जोड़ सकते हैं, जहां प्रत्येक स्ट्रिंग के लिए हम इसे उल्टा करना चुन सकते हैं या नहीं। सभी संभावित लूपों में से, हमें लूप को काटने के बाद लेक्सिकोग्राफ़िक रूप से सबसे बड़ी स्ट्रिंग ढूंढनी होगी, जो लूप वाली स्ट्रिंग को नियमित बना देगा। विशेष रूप से, शब्दावली की दृष्टि से सबसे बड़ी स्ट्रिंग को खोजने के लिए, हमें दो चरणों का अनुभव करने की आवश्यकता है -

सभी स्ट्रिंग्स को एक लूप में संयोजित करें, जहाँ हम कुछ स्ट्रिंग्स को उल्टा कर सकते हैं या नहीं और उन्हें उसी क्रम में जोड़ सकते हैं जैसा कि दिया गया है।

लूप के किसी भी स्थान पर एक कटिंग पॉइंट को काटें और बनाएं, जिससे लूप वाले स्ट्रिंग को कटिंग पॉइंट पर कैरेक्टर से शुरू करके एक नियमित बना दिया जाएगा। और काम सभी संभावित नियमित स्ट्रिंग्स में से लेक्सिकोग्राफिक रूप से सबसे बड़ा खोजना है।

इसलिए, यदि इनपुट "abc", "xyz" जैसा है, तो आउटपुट "zyxcba" होगा क्योंकि हम "-abcxyz-", "-abczyx-", "-cbaxyz-", " -cbazyx-", जहां '-' का उपयोग लूप की स्थिति को दर्शाने के लिए किया जाता है। उत्तर स्ट्रिंग चौथे लूप वाले से आई है, जहां हम मध्य वर्ण 'a' से काट सकते हैं और "zyxcba" प्राप्त कर सकते हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन हल करें () को परिभाषित करें, यह idx, सरणी strs, rev,

  लेगा

• अस्थायी:=strs[idx]

• अगर रेव गैर-शून्य है, तो -

  • सरणी अस्थायी को उलट दें

• str1 :=खाली स्ट्रिंग

• str2 :=खाली स्ट्रिंग

• इनिशियलाइज़ i :=0 के लिए, जब i

  • str1 :=str1 + strs[i]

• प्रारंभ करने के लिए i:=idx + 1, जब i

  • str2 :=str2 + strs[i]

• इनिशियलाइज़ k :=0 के लिए, जब k <टेम्परेचर का आकार, अपडेट करें (1 से k बढ़ाएँ), करें -

  • newOne :=अनुक्रमणिका k से अंत तक अस्थायी का स्थानापन्न str2 समवर्ती str1 अनुक्रमणिका से अस्थायी का संयोजन (0 से k-1)

  • अगर रिट खाली है या रिट

    • रिट :=newOne

• फ़ंक्शन को परिभाषित करें findMax(), यह एक सरणी स्ट्रिंग लेगा,

• प्रारंभ करने के लिए मैं:=0, जब मैं

  • अस्थायी:=strs[i]

  • सरणी अस्थायी को उलट दें

  • strs[i] :=(यदि strs[i]> अस्थायी, फिर strs[i], अन्यथा अस्थायी)

• मुख्य विधि से निम्न कार्य करें -

• रिट:=खाली स्ट्रिंग

• FindMax(strs)

• प्रारंभ करने के लिए मैं:=0, जब मैं

  • हल करें (i, strs, false)

  • हल करें (i, strs, true)

• वापसी रिट

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#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