C++ এ ব্রেস সম্প্রসারণ

ধরুন আমাদের একটি স্ট্রিং S আছে যা শব্দের একটি তালিকা উপস্থাপন করে। এখানে শব্দের প্রতিটি অক্ষরে 1 বা তার বেশি বিকল্প রয়েছে। যদি শুধুমাত্র একটি বিকল্প থাকে, তাহলে অক্ষরটি উপস্থাপন করা হয়। যদি একাধিক বিকল্প থাকে, তাহলে কোঁকড়া ধনুর্বন্ধনী বিকল্পগুলিকে সীমাবদ্ধ করে। সুতরাং উদাহরণস্বরূপ, "{a,b,c}" বিকল্পগুলি উপস্থাপন করবে ["a", "b", "c"]। এখন উদাহরণ স্বরূপ, যদি ইনপুট "{a,b,c}d{e,f}" এর মত হয় তবে এটি ["ade", "adf", "bde", "bdf", "cde" এর প্রতিনিধিত্ব করবে। "cdf"]।

আভিধানিক ক্রমে, এই পদ্ধতিতে গঠিত হতে পারে এমন সমস্ত শব্দ ফেরত দিন।

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

• ret নামক একটি অ্যারে সংজ্ঞায়িত করুন, একটি পূর্ণসংখ্যা টাইপ ভেরিয়েবল n

  সংজ্ঞায়িত করুন

• একটি পদ্ধতি সংজ্ঞায়িত করুন সমাধান(), এটি ইনপুট হিসাবে সূচক, তালিকা এবং curr গ্রহণ করবে

• যদি index =n হয়, তাহলে ret এ curr ঢোকান এবং রিটার্ন করুন

• আমি তালিকার আকার 0 থেকে সীমার জন্য [সূচী]

  • কল সমাধান (সূচী + 1, তালিকা, curr + তালিকা[সূচি, i])

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

• 100 আকারের একটি তালিকা তৈরি করুন, n :=0, পতাকা :=মিথ্যা

  সেট করুন

• 0 থেকে s - 1

  এর আকারের মধ্যে i এর জন্য

  • যদি s[i] কমা হয়, তাহলে পরবর্তী পুনরাবৃত্তিতে চলে যান

  • অন্যথায় যখন s[i] বন্ধনী খুলছে, তখন পতাকা সেট করুন :=true

  • অন্যথায় যখন s[i] বন্ধনী বন্ধ হয়, তখন পতাকা সেট করুন :=মিথ্যা এবং n 1 দ্বারা বাড়ান

  • অন্যথায় s[i] দ্বারা তালিকা[n] বাড়ান, এখন যদি পতাকা মিথ্যা হয়, তাহলে n 1 দ্বারা বাড়ান

• কল সমাধান (0, তালিকা, খালি স্ট্রিং)

• রেট অ্যারে সাজান

• রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector <string> ret;
   int n;
   vector<string> expand(string s) {
      vector <string> list(100);
      n = 0;
      int flag = false;
      for(int i = 0; i < s.size(); i++){
         if(s[i] == ','){
            continue;
         }else if(s[i] == '{'){
            flag = true;
         }else if(s[i] == '}'){
            flag = false;
            n++;
         }else{
            list[n] += s[i];
            if(!flag)n++;
         }
      }
      solve(0, list);
      sort(ret.begin(), ret.end());
      return ret;
   }
   void solve(int idx, vector <string> list, string curr = ""){
      if(idx == n){
         ret.push_back(curr);
         return;
      }
      for(int i = 0; i < list[idx].size(); i++){
         solve(idx + 1, list, curr + list[idx][i]);
      }
   }
};
main(){
   Solution ob;
   print_vector(ob.expand("{a,b}c{d,e}f"));
}

ইনপুট

"{a,b}c{d,e}f"

আউটপুট

[acdf, acef, bcdf, bcef, ]