#1096

Hard

auto_awesomeStack-based state management

LeetCode Problem Workspace

Brace Expansion II

Solve Brace Expansion II efficiently by using stack-based state management to generate all unique combinations of nested string expressions.

string backtracking stack breadth first search

Problem Statement

Given a string expression containing lowercase letters, commas, and curly braces, expand it into all possible unique words according to the following rules. Letters concatenate normally, commas denote a union of options, and braces can contain nested sub-expressions.

For example, the expression "{a,b}{c,{d,e}}" represents all combinations of the first and second sets. Return the result as a list of distinct words sorted lexicographically. The input length is up to 60 characters, and every expression is guaranteed to follow the defined grammar.

Examples

Example 1

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

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

Example details omitted.

Example 2

Input: expression = "{{a,z},a{b,c},{ab,z}}"

Output: ["a","ab","ac","z"]

Each distinct word is written only once in the final answer.

Constraints

1 <= expression.length <= 60
expression[i] consists of '{', '}', ','or lowercase English letters.
The given expression represents a set of words based on the grammar given in the description.

Solution Approach

Use a Stack for State Management

Maintain a stack to track active sets and operators while parsing. Push new sets when encountering '{', and pop when '}' closes a block, merging with the previous set according to union or concatenation rules.

Recursive Parsing for Nested Expressions

Implement a helper function to parse the next 'chunk' of the expression. Recursively evaluate nested braces to return the set of words, ensuring correct order and merging of nested combinations.

Combine Sets for Concatenation and Union

At each step, handle concatenation by forming all possible pairs between sets, and handle union by taking set unions. Sorting and deduplication at the end guarantees the correct lexicographical output.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of resulting words and nested sets, potentially exponential in the worst case due to combinatorial expansion. Space complexity depends on the depth of nesting and size of intermediate sets maintained in the stack.

What Interviewers Usually Probe

Are you correctly managing nested braces with a stack or recursion?
Did you handle concatenation versus union properly during set merges?
Can your approach scale when the number of combinations grows rapidly?

Common Pitfalls or Variants

Common pitfalls

Forgetting to merge intermediate sets properly when exiting a brace block.
Handling duplicates incorrectly, leading to repeated words in the output.
Mixing concatenation and union operations without preserving correct order.

Follow-up variants

Brace Expansion with additional numeric ranges instead of letters.
Expressions allowing optional empty strings in braces, adding empty concatenation cases.
Nested brace expressions with multiple levels and repeated elements requiring deduplication.

FAQ

What is the best approach for parsing Brace Expansion II expressions?

Use a stack-based or recursive method to handle nested braces, unions, and concatenations while building intermediate sets.

How do I avoid duplicate words in the output?

Maintain sets at each stage and perform union operations; ensure final results are deduplicated and sorted lexicographically.

Can this method handle deeply nested expressions efficiently?

Yes, recursion or iterative stack-based parsing ensures correct processing, but combinatorial growth can impact performance.

Should I treat commas and braces differently during parsing?

Yes, commas indicate union while braces define the scope of nested expressions, requiring separate handling in your algorithm.

Does the solution pattern rely on stack-based state management?

Absolutely, stack-based state management is crucial for tracking active sets, nested blocks, and merging operations correctly.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def braceExpansionII(self, expression: str) -> List[str]:
        def dfs(exp):
            j = exp.find('}')
            if j == -1:
                s.add(exp)
                return
            i = exp.rfind('{', 0, j - 1)
            a, c = exp[:i], exp[j + 1 :]
            for b in exp[i + 1 : j].split(','):
                dfs(a + b + c)

        s = set()
        dfs(expression)
        return sorted(s)

Continue Practicing

#488 zuma game #126 word ladder ii #1081 smallest subsequence of distinct characters