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:
R("a") = {"a"}R("w") = {"w"}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)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:
x, we have R(x) = {x}.e1, e2, ... , ek with k >= 2, we have R({e1, e2, ...}) = R(e1) ∪ R(e2) ∪ ...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 <= 60expression[i] consists of '{', '}', ','or lowercase English letters.expression represents a set of words based on the grammar given in the description.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.
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.
Python
JavaScript
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.
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.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| 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. |
| Iterative Stack-Based Approach | Time Complexity: O(n^x), where n is the complexity for nested processing and x is the nested depth. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Parsing with Backtracking | O(n * k) | O(n * k) | Best for recursive parsing of nested brace expressions |
| Iterative Stack-Based Evaluation | O(n * k) | O(n * k) | When avoiding recursion or implementing expression-style parsing |
LeetCode 1096. Brace Expansion II Explanantion and Solution • happygirlzt • 3,284 views views
Watch 9 more video solutions →Practice Brace Expansion II with our built-in code editor and test cases.
Practice on FleetCode