LeetCode 1096: Brace Expansion II

Problem Restatement

We are given a string expression representing a set of strings under a brace expansion language:

• A letter c represents the set {c}.
• {e1, e2, ...} represents the union of the sets.
• e1 e2 (concatenation) represents all strings formed by concatenating one from each.

Return all strings in the resulting set in sorted order.

The official constraints state that 1 <= expression.length <= 60.

Input and Output

Function shape:

def braceExpansionII(expression: str) -> list[str]:
    ...

Examples

Example 1:

expression = "{a,b}{c,{d,e}}"

{a,b} = {a, b}, {c,{d,e}} = {c, d, e}.

Concatenation: {ac, ad, ae, bc, bd, be}.

Answer:

["ac", "ad", "ae", "bc", "bd", "be"]

Key Insight

Use a stack-based approach. Each stack level holds a list of “current groups” being concatenated.

• {: Push a new level onto the stack.
• }: Pop the current level, union its groups, concatenate with the level below.
• ,: Move the current group to the union list and start a new group.
• letter: Extend the current group by concatenating this letter.

Algorithm

1. Maintain a stack where each element is a list of sets (groups separated by commas).
2. Push a new list with one empty-set group when { is seen.
3. On ,: append a new empty group.
4. On }: compute the union of all groups on the top level, pop the level, and concatenate the union with the previous level’s current group.
5. On letter: concatenate the letter to each string in the current group.

Edge Cases

• The stack should store exactly the unresolved items needed by the invariant.
• Process equal values deliberately; many monotonic-stack problems differ only in < versus <=.
• Flush or inspect the remaining stack after the scan if unresolved items still contribute to the answer.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

class Solution:
    def braceExpansionII(self, expression: str) -> list[str]:
        stack = [[{""}]]

        for ch in expression:
            if ch == '{':
                stack.append([{""}])
            elif ch == '}':
                groups = stack.pop()
                union = set().union(*groups)
                cur = stack[-1][-1]
                cur = {a + b for a in cur for b in union}
                stack[-1][-1] = cur
            elif ch == ',':
                stack[-1].append({""})
            else:
                cur = stack[-1][-1]
                cur = {s + ch for s in cur}
                stack[-1][-1] = cur

        return sorted(stack[0][0])

Testing

def run_tests():
    s = Solution()

    assert s.braceExpansionII("{a,b}{c,{d,e}}") == ["ac","ad","ae","bc","bd","be"]
    assert s.braceExpansionII("{{a,z},a{b,c},{ab,z}}") == ["a","ab","ac","z"]

    print("all tests passed")

run_tests()