LeetCode 1096 - Brace Expansion II

LeetCode Problem 1096

Difficulty: 🔴 Hard
Topics: Hash Table, String, Backtracking, Stack, Breadth-First Search, Sorting

Solution

Problem Understanding

The problem asks us to interpret a string expression representing a set of words generated according to a specific grammar and return all distinct words sorted in lexicographical order. The expression can contain lowercase letters, curly braces {}, and commas ,. The rules of the grammar are:

1. A single lowercase letter represents a set containing only that letter.
2. A comma-separated list inside {} represents a union of all expressions within the braces.
3. Concatenation of two expressions represents all possible combinations of words from the first expression followed by words from the second expression.

The input is a string expression with length between 1 and 60, which ensures that we do not need to handle extremely large strings, but the nesting of braces and concatenation can make the set of generated words grow exponentially. The output is a sorted list of all unique words generated from the expression.

Key edge cases include nested braces like "{{a,b},{b,c}}", repeated elements, or deeply concatenated expressions like "a{b,c}{d,e}f{g,h}". A naive approach could easily mismanage nested scopes or duplicate words, so careful parsing and set operations are necessary.

Approaches

The brute-force approach would try to evaluate the expression recursively by generating all combinations, but without proper parsing, it would fail to handle nested braces and unions correctly. This could involve recursively expanding all subexpressions and taking the union of results wherever commas appear. While this is conceptually correct, it would be inefficient and error-prone for deeply nested or concatenated expressions.

The optimal approach involves using a stack-based parser with two types of stacks: one for operands (sets of words) and one for operators (to manage concatenation and union). We process the expression character by character, handling letters, commas, and braces according to precedence rules. The key insight is that we can treat concatenation implicitly whenever two expressions are adjacent, and we only explicitly handle union with commas or end of braces. By using sets at every stage, duplicates are naturally removed.

Algorithm Walkthrough

1. Initialize two stacks: ops for operators and exprs for operand sets.

2. Define a helper function to perform a union of sets and a concatenation of sets.

3. Iterate over the expression character by character:

4. If the character is a lowercase letter, push it as a singleton set onto exprs.

5. If the character is {, push it onto ops to indicate the start of a new subexpression scope.

6. If the character is }, repeatedly pop operators from ops and apply them to sets from exprs until encountering {.

7. If the character is ,, treat it as a union operator. Process any previous concatenation if needed before pushing the union.

8. Implicitly handle concatenation by checking if two sets are adjacent without an operator between them. Multiply the sets to form all possible concatenations.

9. At the end of the iteration, apply any remaining operations to collapse all sets into a final result set.

10. Convert the final set to a sorted list and return.

Why it works: The algorithm maintains the invariant that exprs always contains valid sets for the current scope, and ops controls whether these sets should be unioned or concatenated. By carefully processing braces and commas, the algorithm correctly interprets nested expressions and adjacency-based concatenation.

Python Solution

from typing import List

class Solution:
    def braceExpansionII(self, expression: str) -> List[str]:
        def multiply(set1, set2):
            return {a + b for a in set1 for b in set2}
        
        exprs = []
        ops = []
        
        i = 0
        while i < len(expression):
            char = expression[i]
            if char.isalpha():
                exprs.append({char})
            elif char == '{':
                ops.append(char)
            elif char == '}':
                while ops and ops[-1] != '{':
                    op = ops.pop()
                    set2 = exprs.pop()
                    set1 = exprs.pop()
                    exprs.append(set1.union(set2))
                ops.pop()  # pop the '{'
            elif char == ',':
                while ops and ops[-1] == ',':
                    op = ops.pop()
                    set2 = exprs.pop()
                    set1 = exprs.pop()
                    exprs.append(set1.union(set2))
                ops.append(char)
            
            # Handle implicit concatenation
            if i + 1 < len(expression):
                next_char = expression[i + 1]
                if (char.isalpha() or char == '}') and (next_char.isalpha() or next_char == '{'):
                    set2 = exprs.pop()
                    set1 = exprs.pop()
                    exprs.append(multiply(set1, set2))
            
            i += 1
        
        while ops:
            op = ops.pop()
            set2 = exprs.pop()
            set1 = exprs.pop()
            exprs.append(set1.union(set2))
        
        return sorted(exprs[-1])

The Python implementation uses a stack-based parsing approach. Each letter is pushed as a singleton set. Braces manage scope, and commas indicate union operations. Implicit concatenation is handled by checking adjacency of expressions. The multiply helper ensures that concatenation produces all possible combinations, and the final result is sorted.

Go Solution

package main

import (
	"sort"
)

func braceExpansionII(expression string) []string {
	multiply := func(a, b map[string]struct{}) map[string]struct{} {
		res := make(map[string]struct{})
		for x := range a {
			for y := range b {
				res[x+y] = struct{}{}
			}
		}
		return res
	}

	exprs := []map[string]struct{}{}
	ops := []rune{}

	addSet := func(s map[string]struct{}) {
		exprs = append(exprs, s)
	}

	i := 0
	for i < len(expression) {
		char := expression[i]
		if char >= 'a' && char <= 'z' {
			addSet(map[string]struct{}{string(char): {}})
		} else if char == '{' {
			ops = append(ops, '{')
		} else if char == '}' {
			for len(ops) > 0 && ops[len(ops)-1] != '{' {
				op := ops[len(ops)-1]
				ops = ops[:len(ops)-1]
				set2 := exprs[len(exprs)-1]
				exprs = exprs[:len(exprs)-1]
				set1 := exprs[len(exprs)-1]
				exprs = exprs[:len(exprs)-1]
				for k := range set2 {
					set1[k] = struct{}{}
				}
				exprs = append(exprs, set1)
			}
			ops = ops[:len(ops)-1] // pop '{'
		} else if char == ',' {
			for len(ops) > 0 && ops[len(ops)-1] == ',' {
				op := ops[len(ops)-1]
				ops = ops[:len(ops)-1]
				set2 := exprs[len(exprs)-1]
				exprs = exprs[:len(exprs)-1]
				set1 := exprs[len(exprs)-1]
				exprs = exprs[:len(exprs)-1]
				for k := range set2 {
					set1[k] = struct{}{}
				}
				exprs = append(exprs, set1)
			}
			ops = append(ops, ',')
		}

		// Handle implicit concatenation
		if i+1 < len(expression) {
			next_char := expression[i+1]
			if (char >= 'a' && char <= 'z' || char == '}') && (next_char >= 'a' && next_char <= 'z' || next_char == '{') {
				set2 := exprs[len(exprs)-1]
				exprs = exprs[:len(exprs)-1]
				set1 := exprs[len(exprs)-1]
				exprs = exprs[:len(exprs)-1]
				exprs = append(exprs, multiply(set1, set2))
			}
		}

		i++
	}

	for len(ops) > 0 {
		op := ops[len(ops)-1]
		ops = ops[:len(ops)-1]
		set2 := exprs[len(exprs)-1]
		exprs = exprs[:len(exprs)-1]
		set1 := exprs[len(exprs)-1]
		exprs = exprs[:len(exprs)-1]
		for k := range set2 {
			set1[k] = struct{}{}
		}
		exprs = append(exprs, set1)
	}

	res := make([]string, 0, len(exprs[0]))
	for k := range exprs[0] {
		res = append(res, k)
	}
	sort.Strings(res)
	return res
}

The Go solution mirrors the Python stack-based approach. The main difference is the use of map[string]struct{} to represent sets, as Go does not have a built-in set