Watch 10 video solutions for Brace Expansion II, a hard level problem involving String, Backtracking, Stack. This walkthrough by happygirlzt has 3,284 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |