1076. Brace Expansion

• Difficulty: Medium

• Topics: Backtracking

• Similar Questions:

  • Decode String

  • Letter Case Permutation

  • Brace Expansion II

Problem:

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.

Solutions:

class Solution {
public:
    vector<string> expand(string S) {
        set<string> ret;
        string path;
        helper(S, 0, path, ret);
        return {ret.begin(), ret.end()};
    }

private:
    void helper(const string& S, int pos, string& path, set<string>& ret) {
        if (pos == S.length()) {
            ret.insert(path);
            return;
        }

        string origin = path;
        while (pos < S.length() && S[pos] != '{') {
            path.push_back(S[pos++]);
        }

        if (S[pos] == '{') {
            ++pos; 
            vector<char> letters;
            while (S[pos] != '}') {
                if (S[pos] == ',') {
                    ++pos;
                } else {
                    letters.push_back(S[pos++]);
                }
            }

            for (char& c : letters) {
                path.push_back(c);
                helper(S, pos + 1, path, ret);
                path.pop_back();
            }
            path = origin;
            return;
        }

        ret.insert(path);
        path = origin;
        return;
    }

};