C++ এ সংযুক্ত স্ট্রিংগুলিকে বিভক্ত করুন

ধরুন আমাদের স্ট্রিংগুলির একটি তালিকা আছে, আমরা এই স্ট্রিংগুলিকে একটি লুপে একত্রিত করতে পারি, যেখানে প্রতিটি স্ট্রিংয়ের জন্য আমরা এটিকে বিপরীত বা না বেছে নিতে পারি। সম্ভাব্য লুপগুলির মধ্যে, লুপটি কাটার পরে আমাদের অভিধানিকভাবে সবচেয়ে বড় স্ট্রিংটি খুঁজে বের করতে হবে, যা লুপ করা স্ট্রিংটিকে একটি নিয়মিত স্ট্রিংতে পরিণত করবে। বিশেষ করে, অভিধানগতভাবে সবচেয়ে বড় স্ট্রিং খুঁজে পেতে, আমাদের দুটি পর্যায় অনুভব করতে হবে -

সমস্ত স্ট্রিংগুলিকে একটি লুপে সংযুক্ত করুন, যেখানে আমরা কিছু স্ট্রিংকে বিপরীত করতে পারি বা না করতে পারি এবং সেগুলিকে দেওয়া একই ক্রমে সংযুক্ত করতে পারি৷

লুপের যেকোন জায়গায় একটি কাটিং পয়েন্ট কাট এবং তৈরি করুন, যা লুপ করা স্ট্রিংটিকে কাটিং পয়েন্টের অক্ষর থেকে শুরু করে একটি রেগুলারে পরিণত করবে। এবং কাজ হল সমস্ত সম্ভাব্য নিয়মিত স্ট্রিংগুলির মধ্যে অভিধানগতভাবে সবচেয়ে বড়টি খুঁজে বের করা৷

সুতরাং, যদি ইনপুট "abc", "xyz" এর মত হয়, তাহলে আউটপুট হবে "zyxcba" কারণ আমরা লুপ করা স্ট্রিং যেমন "-abcxyz-", "-abczyx-", "-cbaxyz-", " -cbazyx-”, যেখানে '-' ব্যবহার করা হয় লুপড স্ট্যাটাস উপস্থাপন করতে। উত্তর স্ট্রিংটি এসেছে চতুর্থ লুপড থেকে, যেখানে আমরা মধ্যম অক্ষর 'a' থেকে কেটে "zyxcba" পেতে পারি।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন সল্ভ() সংজ্ঞায়িত করুন, এটি idx, array strs, rev,

  নেবে

• temp :=strs[idx]

• যদি রেভ অ-শূন্য হয়, তাহলে −

  • অ্যারের তাপমাত্রা বিপরীত করুন

• str1 :=খালি স্ট্রিং

• str2 :=খালি স্ট্রিং

• আরম্ভ করার জন্য i :=0, যখন i

  • str1 :=str1 + strs[i>

• আরম্ভ করার জন্য i :=idx + 1, যখন i

  • str2 :=str2 + strs[i>

• আরম্ভ করার জন্য k :=0, যখন k <তাপমাত্রার আকার, আপডেট করুন (k 1 দ্বারা বৃদ্ধি করুন), করুন −

  • newOne :=সূচক k থেকে শেষ পর্যন্ত temp-এর সাবস্ট্রিং str2 concatenate str1 সূচক থেকে temp-এর concatenate সাবস্ট্রিং (0 থেকে k-1)

  • যদি ret খালি হয় বা ret

    • ret :=newOne

• একটি ফাংশন findMax() সংজ্ঞায়িত করুন, এটি একটি অ্যারে স্ট্রার্স নেবে,

• আরম্ভ করার জন্য i :=0, যখন i

  • temp :=strs[i]

  • অ্যারে টেম্প রিভার্স করুন

  • strs[i] :=(যদি strs[i]> temp, তারপর strs[i], অন্যথায় temp)

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• ret :=খালি স্ট্রিং

• FindMax(strs)

• আরম্ভ করার জন্য i :=0, যখন i

  • সমাধান (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