Brace Expansion ใน C++

ปัญหา

ให้ String S แทนรายการคำ โดยตัวอักษรแต่ละตัวมีตัวเลือก 1 หรือหลายตัว

• ตัวเลือกเดียว: เขียนตัวอักษรเลย (เช่น 'a')
• หลายตัวเลือก: ใช้ {} ครอบ คั่นด้วย comma (เช่น {a,b,c})

ตัวอย่าง: "{a,b}c{d,e}f" → ["acdf", "acef", "bcdf", "bcef"] (เรียง Lexicographic)

อัลกอริทึม: Parse + Backtracking

1. Parse String → Array of Options (แต่ละตำแหน่งมี vector<char>)
2. Backtracking สร้างทุก Combination
3. Sort ผลลัพธ์

ตัวอย่างโค้ด C++

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

class Solution {
public:
    vector<string> expand(string s) {
        vector<string> options;
        string curr;
        bool in_brace = false;
        
        // Parse
        for (char c : s) {
            if (c == '{') {
                in_brace = true;
                curr.clear();
            } else if (c == '}') {
                in_brace = false;
                // Split curr by comma
                stringstream ss(curr);
                string opt;
                while (getline(ss, opt, ','))
                    options.push_back(opt);
                curr.clear();
            } else if (c == ',') {
                continue; // Skip comma
            } else {
                curr += c;
                if (!in_brace) {
                    options.push_back(curr);
                    curr.clear();
                }
            }
        }
        
        // Backtracking
        vector<string> result;
        function<void(int, string)> dfs = [&](int idx, string path) {
            if (idx == options.size()) {
                result.push_back(path);
                return;
            }
            for (char c : options[idx])
                dfs(idx + 1, path + c);
        };
        
        dfs(0, "");
        sort(result.begin(), result.end());
        return result;
    }
};

int main() {
    Solution ob;
    auto res = ob.expand("{a,b}c{d,e}f");
    for (auto& str : res) cout << str << " ";
    // acdf acef bcdf bcef
    return 0;
}

ผลลัพธ์

acdf acef bcdf bcef

Complexity

• Time: O(K × N log N) โดย K = จำนวน Combinations, N = ความยาว String
• Space: O(K × N)