1096. Brace Expansion II

String
Backtracking
Stack
Breadth-First Search

TIME

O(total output size * word length)

SPACE

O(total output size)

Intuition

The grammar in the statement is already a parser specification, with the usual precedence: concatenation binds tighter than the comma. Writing it as three mutually recursive functions makes the two set operations fall out directly, one per production.

union  := concat (',' concat)*      -> set union of the parts
concat := term+                     -> pairwise concatenation (cartesian product)
term   := letter | '{' union '}'    -> singleton, or recurse

Using a set at every level means duplicates collapse the moment they appear, so {{a,b},{b,c}} needs no extra work, and neither does the repeated a in Example 2.

Approach

Carry a single mutable index into the expression.

parse_union: parse a concat, then while the next character is ,, consume it and parse another concat, unioning the results.
parse_concat: start from {""} and, while the next character is neither , nor } nor end of input, parse a term and replace the accumulator with {a + b} over the cross product.
parse_term: on {, consume it, parse_union, consume the matching }. Otherwise consume one letter and return a singleton.
Call parse_union at index 0 and return the sorted result.

Because parse_concat halts on , and }, the caller always sees those delimiters and the recursion stays in step with the braces without any explicit depth counter.

Complexity

Time: O(total output size * word length), each parse step touches one character, and the set products build the words
Space: O(total output size)

With 60 input characters, the widest output comes from repeated small alternation blocks: {a,b,c} is 7 characters, so 8 of them give 3^8 = 6561 words. Nothing here explodes.

Edge Cases

A bare letter, "a" → ["a"], no braces at all
Nested unions inside a concatenation, "{a,b}{c,{d,e}}" (Example 1)
Duplicates arising from different branches, "{{a,z},a{b,c},{ab,z}}" (Example 2)
Words of differing lengths in the same union (a and ab in Example 2); sorting is plain lexicographic, so "a" precedes "ab"
A union nested immediately inside another, "{{a,b}}" → ["a","b"]
parse_concat must seed with the single empty string rather than an empty set, or the product with the first term would collapse to nothing

Code

from typing import List, Set


class Solution:
    def braceExpansionII(self, expression: str) -> List[str]:
        """
        1096. Brace Expansion II
        Time: O(total output size * word length)
        Space: O(total output size)
        """
        n = len(expression)
        self.pos = 0

        def parse_union() -> Set[str]:
            words = parse_concat()
            while self.pos < n and expression[self.pos] == ",":
                self.pos += 1  # skip ','
                words |= parse_concat()
            return words

        def parse_concat() -> Set[str]:
            words = {""}
            while self.pos < n and expression[self.pos] not in ",}":
                part = parse_term()
                words = {a + b for a in words for b in part}
            return words

        def parse_term() -> Set[str]:
            if expression[self.pos] == "{":
                self.pos += 1  # skip '{'
                words = parse_union()
                self.pos += 1  # skip '}'
                return words
            ch = expression[self.pos]
            self.pos += 1
            return {ch}

        return sorted(parse_union())

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

/**
 * 1096. Brace Expansion II
 * Time: O(total output size * word length)
 * Space: O(total output size)
 */
class Solution {
    private String expr;
    private int pos;

    public List<String> braceExpansionII(String expression) {
        expr = expression;
        pos = 0;
        return new ArrayList<>(new TreeSet<>(parseUnion()));
    }

    /** union := concat (',' concat)* */
    private Set<String> parseUnion() {
        Set<String> words = parseConcat();
        while (pos < expr.length() && expr.charAt(pos) == ',') {
            pos++;  // skip ','
            words.addAll(parseConcat());
        }
        return words;
    }

    /** concat := term+ */
    private Set<String> parseConcat() {
        Set<String> words = new HashSet<>();
        words.add("");
        while (pos < expr.length() && expr.charAt(pos) != ',' && expr.charAt(pos) != '}') {
            Set<String> part = parseTerm();
            Set<String> merged = new HashSet<>();
            for (String a : words) {
                for (String b : part) {
                    merged.add(a + b);
                }
            }
            words = merged;
        }
        return words;
    }

    /** term := letter | '{' union '}' */
    private Set<String> parseTerm() {
        if (expr.charAt(pos) == '{') {
            pos++;  // skip '{'
            Set<String> words = parseUnion();
            pos++;  // skip '}'
            return words;
        }
        Set<String> single = new HashSet<>();
        single.add(String.valueOf(expr.charAt(pos)));
        pos++;
        return single;
    }
}