Skip to main content
Talentd

Brace Expansion II - Solution & Explanation

HardStringBacktrackingStackBreadth-First Search10 min readAsked at: Google
Practice this problem

Problem Statement

Under the grammar given below, strings can represent a set of lowercase words. Let R(expr) denote the set of words the expression represents.

The grammar can best be understood through simple examples:

  • Single letters represent a singleton set containing that word.
    • R("a") = {"a"}
    • R("w") = {"w"}
  • When we take a comma-delimited list of two or more expressions, we take the union of possibilities.
    • R("{a,b,c}") = {"a","b","c"}
    • R("{{a,b},{b,c}}") = {"a","b","c"} (notice the final set only contains each word at most once)
  • When we concatenate two expressions, we take the set of possible concatenations between two words where the first word comes from the first expression and the second word comes from the second expression.
    • R("{a,b}{c,d}") = {"ac","ad","bc","bd"}
    • R("a{b,c}{d,e}f{g,h}") = {"abdfg", "abdfh", "abefg", "abefh", "acdfg", "acdfh", "acefg", "acefh"}

Formally, the three rules for our grammar:

  • For every lowercase letter x, we have R(x) = {x}.
  • For expressions e1, e2, ... , ek with k >= 2, we have R({e1, e2, ...}) = R(e1) ∪ R(e2) ∪ ...
  • For expressions e1 and e2, we have R(e1 + e2) = {a + b for (a, b) in R(e1) × R(e2)}, where + denotes concatenation, and × denotes the cartesian product.

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

 

Example 1:

Input: expression = "{a,b}{c,{d,e}}"
Output: ["ac","ad","ae","bc","bd","be"]

Example 2:

Input: expression = "{{a,z},a{b,c},{ab,z}}"
Output: ["a","ab","ac","z"]
Explanation: 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.

Approach Overview

Problem Overview: You are given a string expression that contains lowercase letters, commas, and curly braces. Braces represent union operations while adjacent expressions represent concatenation. The task is to expand the expression and return all possible strings in sorted order without duplicates.

Approach 1: Depth-First Parsing with Backtracking (O(n * k) time, O(n * k) space)

This approach recursively parses the expression and builds results using set operations. Treat commas as union and adjacency as concatenation. During parsing, maintain a current set of strings and combine it with the next parsed component using Cartesian product logic. When encountering a {, recursively evaluate until the matching }, then merge the results. Sets automatically remove duplicates and make union operations straightforward.

The key insight is that brace expressions behave like a small grammar: union (comma) and concatenation (adjacent tokens). DFS naturally models this structure because nested braces become recursive calls. This method is clean and easy to reason about, especially when implementing with backtracking and recursive string parsing.

Approach 2: Iterative Stack-Based Expression Evaluation (O(n * k) time, O(n * k) space)

This method evaluates the expression iteratively using stacks, similar to parsing arithmetic expressions. Maintain stacks for intermediate result sets and operators. When encountering letters, push them as singleton sets. When encountering {, start a new evaluation frame. Commas represent union operations while adjacency triggers concatenation between the top sets.

When } appears, resolve all operations inside that brace level and push the combined result back to the previous frame. Concatenation is handled by generating the product of two sets, while union merges them. Using stacks avoids recursion depth issues and mirrors classic expression parsing patterns. The approach relies heavily on a stack to track nested scopes and operators.

Recommended for interviews: The depth-first parsing approach is usually preferred. It clearly models the grammar of brace expressions and demonstrates strong recursion and parsing skills. Interviewers expect candidates to recognize union vs concatenation and handle nested braces correctly. The stack-based solution shows deeper knowledge of expression evaluation and is useful if you want to avoid recursion or demonstrate iterative parsing techniques.

Approach 1: Depth-First Parsing Approach

This approach involves parsing the expression recursively. By evaluating the expression in a depth-first manner, you can handle nested structures and perform set operations (union and Cartesian product) to build up the set of possible words.

Use a recursive function to handle expressions within braces and different operations between them.

This Python solution uses a recursive helper function evaluate that processes the input string based on parsing depth-first manner using a stack. The function finds and processes sub-expressions recursively. It performs set operations—union and concatenation—to evaluate the possible sets resulting from the input expression.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n^k) in the worst case, where n is the length of the expression and k is the number of nested braces and operations.
Space Complexity: O(n^k), due to multiple recursive calls and storage of intermediate results in sets.

Try this approach in the editor →

Approach 2: Iterative Stack-Based Approach

This approach uses an explicit stack to manage operations iteratively. The expression is parsed character by character, pushing operations and sets onto the stack for processing in the correct order. This method harnesses the stack data structure to avoid recursion, primarily controlling the flow with loops and stack manipulation.

This Java solution employs two stacks: one for operators (chromatically stacking characters like '{' and ','), and one for sets to manage the Union and Cartesian Product operations. The process is iterative, parsing the expression without recursion and building sets within braces.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(n^x), where n is the complexity for nested processing and x is the nested depth.
Space Complexity: O(n^x) for storing intermediate sets due to stack operations during processing.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Depth-First Parsing Approach

Time Complexity: O(n^k) in the worst case, where n is the length of the expression and k is the number of nested braces and operations.
Space Complexity: O(n^k), due to multiple recursive calls and storage of intermediate results in sets.

Iterative Stack-Based Approach

Time Complexity: O(n^x), where n is the complexity for nested processing and x is the nested depth.
Space Complexity: O(n^x) for storing intermediate sets due to stack operations during processing.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Depth-First Parsing with BacktrackingO(n * k)O(n * k)Best for recursive parsing of nested brace expressions
Iterative Stack-Based EvaluationO(n * k)O(n * k)When avoiding recursion or implementing expression-style parsing

Video Solution

LeetCode 1096. Brace Expansion II Explanantion and Solution • happygirlzt • 3,348 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Brace Expansion II easy or hard?
Brace Expansion II is classified as a Hard problem because it combines parsing, recursion, and set-based combination logic. Handling nested braces, union operations, and concatenation correctly requires careful expression evaluation design.
Brace Expansion II Python/Java solution
Python solutions usually implement recursive DFS parsing with sets and string concatenation. Java solutions often use iterative stack-based parsing with HashSet structures to track partial expansions. Both approaches run in roughly O(n * k) time.
How to solve Brace Expansion II in O(n)?
A strict O(n) solution is not possible because the algorithm must generate every expanded string. The best achievable complexity is proportional to the output size, typically O(n * k). Efficient implementations minimize overhead by using sets and combining partial results only when necessary.
What is the best approach for Brace Expansion II?
Depth-first parsing with backtracking is the most common approach. It treats the expression like a grammar with union and concatenation operations and recursively evaluates nested braces. Using sets ensures duplicates are removed automatically. The time complexity is roughly O(n * k), where k is the number of generated strings.
Is Brace Expansion II asked at Google/Amazon/Meta?
Brace-style parsing problems appear in interviews at companies like Google and Amazon because they test recursion, parsing, and data structure usage. Variations of expression parsing and grammar evaluation are common system and algorithm interview topics.
What data structure is used in Brace Expansion II?
Typical implementations use sets to store unique intermediate strings and either recursion or stacks to manage nested braces. Stacks help evaluate expressions iteratively, while recursion naturally handles nested parsing structures.
What is the time complexity of Brace Expansion II?
The time complexity is O(n * k), where n is the length of the expression and k is the total number of generated output strings. Each expansion step may combine sets of strings using Cartesian products. The space complexity is also O(n * k) because all generated strings must be stored.

Ready to solve this problem?

Practice Brace Expansion II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Brace Expansion