1096. Brace Expansion II

class Solution:
    def braceExpansionII(self, expression):
        self.s = expression
        self.i = 0

        result = self.parse()
        return sorted(result)

    def parse(self):
        result = {""}

        while self.i < len(self.s) and self.s[self.i] != '}':
            if self.s[self.i] == ',':
                break

            next_set = self.parse_single()
            result = {
                a + b
                for a in result
                for b in next_set
            }

        return result

    def parse_single(self):
        if self.s[self.i] == '{':
            self.i += 1
            result = set()

            while True:
                result.update(self.parse())

                if self.i < len(self.s) and self.s[self.i] == ',':
                    self.i += 1
                else:
                    break

            self.i += 1
            return result

        ch = self.s[self.i]
        self.i += 1
        return {ch}

class Solution:
    def braceExpansionII(self, expression):
        self.s = expression
        self.i = 0

        result = self.parse()
        return sorted(result)

    def parse(self):
        result = {""}

        while self.i < len(self.s) and self.s[self.i] != '}':
            if self.s[self.i] == ',':
                break

            next_set = self.parse_single()
            result = {
                a + b
                for a in result
                for b in next_set
            }

        return result

    def parse_single(self):
        if self.s[self.i] == '{':
            self.i += 1
            result = set()

            while True:
                result.update(self.parse())

                if self.i < len(self.s) and self.s[self.i] == ',':
                    self.i += 1
                else:
                    break

            self.i += 1
            return result

        ch = self.s[self.i]
        self.i += 1
        return {ch}

class Solution {
private:
    string s;
    int idx;

    set<string> parse() {
        set<string> result = {""};

        while (idx < s.size() && s[idx] != '}') {
            if (s[idx] == ',')
                break;

            set<string> next = parseSingle();
            result = cartesian(result, next);
        }

        return result;
    }

    set<string> parseSingle() {
        set<string> result;

        if (s[idx] == '{') {
            idx++;

            while (true) {
                set<string> part = parse();
                result.insert(part.begin(), part.end());

                if (s[idx] == ',') {
                    idx++;
                } else {
                    break;
                }
            }

            idx++;
        } else {
            result.insert(string(1, s[idx]));
            idx++;
        }

        return result;
    }

    set<string> cartesian(const set<string>& a,
                          const set<string>& b) {
        set<string> result;

        for (const string& x : a) {
            for (const string& y : b) {
                result.insert(x + y);
            }
        }

        return result;
    }

public:
    vector<string> braceExpansionII(string expression) {
        s = expression;
        idx = 0;

        set<string> result = parse();

        return vector<string>(result.begin(), result.end());
    }
};

class Solution {
    braceExpansionII(expression) {
        this.s = expression;
        this.idx = 0;

        const result = this.parse();

        return [...result].sort();
    }

    parse() {
        let result = new Set([""]);

        while (
            this.idx < this.s.length &&
            this.s[this.idx] !== '}'
        ) {
            if (this.s[this.idx] === ',') {
                break;
            }

            const next = this.parseSingle();
            const combined = new Set();

            for (const a of result) {
                for (const b of next) {
                    combined.add(a + b);
                }
            }

            result = combined;
        }

        return result;
    }

    parseSingle() {
        if (this.s[this.idx] === '{') {
            this.idx++;

            const result = new Set();

            while (true) {
                const part = this.parse();

                for (const word of part) {
                    result.add(word);
                }

                if (this.s[this.idx] === ',') {
                    this.idx++;
                } else {
                    break;
                }
            }

            this.idx++;
            return result;
        }

        const ch = this.s[this.idx++];
        return new Set([ch]);
    }
}