LeetCode Solutions Blog

Brace Expansion II

Difficulty: Hard

Problem Description

Given an expression representing a set of words under a specific grammar, return the sorted list of words that the expression represents.

Key Insights

The grammar allows for single letters, unions of sets, and concatenation of sets.
Each expression can be nested, meaning we must handle combinations of combinations.
Distinct words should be returned in sorted order.

Space and Time Complexity

Time Complexity: O(n * 2^m), where n is the length of the expression and m is the maximum number of unique words generated. Space Complexity: O(m), where m is the number of unique words generated.

Solution

The solution involves using a stack to parse the expression and build sets of words according to the defined grammar rules. We will use a recursive approach to handle nested expressions and concatenate words from different sets. The final result will be stored in a set to ensure uniqueness before sorting.

Code Solutions

def braceExpansionII(expression: str) -> List[str]:
    def parse_expression(expr):
        stack = []
        cur_set = set()
        i = 0
        
        while i < len(expr):
            if expr[i] == '{':
                j = i
                brace_count = 0
                while j < len(expr):
                    if expr[j] == '{':
                        brace_count += 1
                    elif expr[j] == '}':
                        brace_count -= 1
                    if brace_count == 0:
                        break
                    j += 1
                inner_set = parse_expression(expr[i + 1:j])
                cur_set = cur_set.union(inner_set)
                i = j + 1
            elif expr[i] == '}':
                break
            elif expr[i] == ',':
                i += 1
            else:
                cur_set.add(expr[i])
                i += 1
        
        return cur_set
    
    def concat_sets(set1, set2):
        return {a + b for a in set1 for b in set2}
    
    expr_sets = []
    i = 0
    while i < len(expression):
        if expression[i] == '{':
            j = i
            brace_count = 0
            while j < len(expression):
                if expression[j] == '{':
                    brace_count += 1
                elif expression[j] == '}':
                    brace_count -= 1
                if brace_count == 0:
                    break
                j += 1
            expr_sets.append(parse_expression(expression[i + 1:j]))
            i = j + 1
        elif expression[i].isalpha():
            expr_sets.append({expression[i]})
            i += 1
        else:
            i += 1

    result = expr_sets[0]
    for s in expr_sets[1:]:
        result = concat_sets(result, s)
    
    return sorted(result)