ব্রেস এক্সপ্যানশন (Brace Expansion) (C++)

এই সমস্যায় একটি স্ট্রিং S দেওয়া আছে যা শব্দের তালিকা রিপ্রেজেন্ট করে। ক্যারেক্টারগুলোর অপশন থাকে: একটার থাকলে সরাসরি লিখা থাকে, একাধিক হলে কালি ব্রেস {} দিয়ে কমা-সেপারেটেড অপশন দেওয়া থাকে। সব সম্ভাব্য শব্দ লেক্সিকোগ্রাফিক ক্রমে ফেরত দিতে হবে।

উদাহরণ

ইনপুট: "{a,b}c{d,e}f"

আউটপুট: [acdf, acef, bcdf, bcef]

অ্যালগরিদম (ব্যাকট্র্যাকিং)

1. স্ট্রিং পার্স করে প্রতিটি পজিশনের অপশনগুলো একটি ভেক্টরে রাখুন।
2. রিকার্শিভ ব্যাকট্র্যাকিং দিয়ে সব কবিনেশন জেনারেট করুন।
3. ফলাফল সর্ট করুন।

C++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;

class Solution {
    vector<string> result;
    int n;

    void solve(int idx, vector<string>& list, string curr = "") {
        if (idx == n) {
            result.push_back(curr);
            return;
        }
        for (int i = 0; i < list[idx].size(); i++)
            solve(idx + 1, list, curr + list[idx][i]);
    }

public:
    vector<string> expand(string s) {
        vector<string> list(100);
        n = 0;
        bool inBrace = false;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ',') continue;
            else if (s[i] == '{') inBrace = true;
            else if (s[i] == '}') { inBrace = false; n++; }
            else {
                list[n] += s[i];
                if (!inBrace) n++;
            }
        }
        solve(0, list);
        sort(result.begin(), result.end());
        return result;
    }
};

void print_vector(vector<string> v) {
    cout << "[";
    for (auto& s : v) cout << s << ", ";
    cout << "]" << endl;
}

int main() {
    Solution ob;
    print_vector(ob.expand("{a,b}c{d,e}f"));
    return 0;
}

আউটপুট

[acdf, acef, bcdf, bcef, ]