1087. Brace Expansion

A string S represents a list of words.

Each letter in the word has 1 or more options. If there is one option, the letter is represented as is. If there is more than one option, then curly braces delimit the options. For example, "{a,b,c}" represents options ["a", "b", "c"].

For example, "{a,b,c}d{e,f}" represents the list ["ade", "adf", "bde", "bdf", "cde", "cdf"].

Return all words that can be formed in this manner, in lexicographical order.

Example 1:

Input: "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

Example 2:

Input: "abcd"
Output: ["abcd"]

Note:

1. 1 <= S.length <= 50

2. There are no nested curly brackets.

3. All characters inside a pair of consecutive opening and ending curly brackets are different.

// Recursive Backtracking
void helper(const string& s, int idx, string& cur, vector<string>& res) {
    if (idx == s.length()) {
        if (!cur.empty()) res.push_back(cur);
        return;
    }
    char c = s[idx];
    if (c == '{') {
        string chars; // potential character options
        int curIdx = idx + 1;
        while (curIdx < s.length() && s[curIdx] != '}') {
            if (s[curIdx] >= 'a' && s[curIdx] <= 'z') chars.push_back(s[curIdx]);
            ++curIdx;
        }
        // sorting for lexicographical order
        sort(chars.begin(), chars.end());
        // backtracking
        for (char ch : chars) {
            cur.push_back(ch);
            helper(s, curIdx + 1, cur, res);
            cur.pop_back();
        }
    } else if (c >= 'a' && c <= 'z') {
        cur.push_back(c);
        helper(s, idx + 1, cur, res);
        cur.pop_back();
    }
}
vector<string> expand(string S) { // time: O(2^n); space: O(n)
    string cur;
    vector<string> res;
    helper(S, 0, cur, res);
    return res;
}