Brace Expansion II
HardPrompt
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 haveR(x) = {x}. - For expressions
e1, e2, ... , ekwithk >= 2, we haveR({e1, e2, ...}) = R(e1) ∪ R(e2) ∪ ... - For expressions
e1ande2, we haveR(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.- The given
expressionrepresents a set of words based on the grammar given in the description.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a standard recursive descent parser to interpret the grammar. It recursively evaluates expressions, terms, and factors. Intermediate results are stored in lists. Concatenation is handled by taking the Cartesian product of two lists, and union is handled by merging lists. Since lists can contain duplicates, a final step is required to remove duplicates and sort the results.
Algorithm
- Implement a recursive function
parseExpr()that returns aList<String>. - Inside
parseExpr(), create an empty listunionList. - Loop to parse terms separated by commas:
- Call a
parseTerm()function to get aList<String>for the current term. - Add all elements from the term's list to
unionList. - If the next character is a comma, consume it and continue. Otherwise, break.
- Call a
- Return
unionList. - Implement
parseTerm()which returns aList<String>. - Initialize
productListwith a list containing one empty string:[""]. - Loop as long as the next part of the expression is a factor (starts with a letter or
{):- Call
parseFactor()to get a list for the factor. - Compute the Cartesian product of
productListand the factor's list, storing it in a new list. - Replace
productListwith the new list.
- Call
- Return
productList. - Implement
parseFactor()which returns aList<String>.- If the character is
{, consume it, recursively callparseExpr(), consume}, and return the result. - If the character is a letter, read the entire word and return a list containing just that word.
- If the character is
- In the main function, call
parseExpr()on the whole expression. - Convert the resulting list to a
HashSetto get unique words. - Convert the
HashSetto anArrayListand sort it.
Walkthrough
We model the grammar with mutually recursive functions: parseExpr, parseTerm, and parseFactor. A global pointer pos is used to keep track of the current position in the expression string.
parseExprhandles comma-separated unions (theR({e1, e2, ...})rule). It callsparseTermfor each expression part and combines the resulting lists of words.parseTermhandles concatenation (theR(e1 + e2)rule). It callsparseFactorrepeatedly for each concatenated element and computes the Cartesian product of the resulting lists.parseFactorhandles the base cases: single letters (or words) and nested expressions within curly braces ({...}). For nested expressions, it makes a recursive call toparseExprto evaluate the content inside the braces.
All these functions return a List<String>. The main function initiates the parsing, and once the final list of all possible words is generated, it converts this list to a Set to eliminate duplicates, and then converts it back to a new list which is then sorted.
import java.util.*; class Solution { int pos = 0; String expression; public List<String> braceExpansionII(String expression) { this.expression = expression; this.pos = 0; List<String> resultList = parseExpr(); // Deduplicate and sort Set<String> resultSet = new HashSet<>(resultList); List<String> sortedList = new ArrayList<>(resultSet); Collections.sort(sortedList); return sortedList; } // An expression is a comma-separated list of terms. private List<String> parseExpr() { List<String> unionList = new ArrayList<>(); while (true) { unionList.addAll(parseTerm()); if (pos < expression.length() && expression.charAt(pos) == ',') { pos++; // Consume ',' } else { break; } } return unionList; } // A term is a concatenation of factors. private List<String> parseTerm() { List<String> productList = new ArrayList<>(); productList.add(""); // Identity for concatenation while (pos < expression.length() && (Character.isLetter(expression.charAt(pos)) || expression.charAt(pos) == '{')) { List<String> factorList = parseFactor(); List<String> newProductList = new ArrayList<>(); for (String s1 : productList) { for (String s2 : factorList) { newProductList.add(s1 + s2); } } productList = newProductList; } return productList; } // A factor is a single word or a nested expression. private List<String> parseFactor() { if (expression.charAt(pos) == '{') { pos++; // Consume '{' List<String> result = parseExpr(); pos++; // Consume '}' return result; } else { // Letter StringBuilder sb = new StringBuilder(); while (pos < expression.length() && Character.isLetter(expression.charAt(pos))) { sb.append(expression.charAt(pos)); pos++; } List<String> result = new ArrayList<>(); result.add(sb.toString()); return result; } }}Complexity
Time
O(N + C_dup * L_avg), where `N` is the expression length, `C_dup` is the total number of words generated including duplicates, and `L_avg` is the average word length. `C_dup` can be much larger than the number of unique words, making this approach less efficient.
Space
O(N + C_dup * L_avg), where `N` is the expression length, `C_dup` is the total number of words generated including duplicates, and `L_avg` is the average word length. This space is used for the recursion stack and for storing the lists of words.
Trade-offs
Pros
Conceptually straightforward mapping of the grammar to code.
Relatively easy to implement the parsing logic.
Cons
Inefficient due to creating potentially large lists with many duplicate strings.
The final deduplication and sorting step can be slow if the number of generated (non-unique) words is very large.
Solutions
Solution
class Solution {private TreeSet<String> s = new TreeSet<>();public List<String> braceExpansionII(String expression) { dfs(expression); return new ArrayList<>(s); }private void dfs(String exp) { int j = exp.indexOf('}'); if (j == -1) { s.add(exp); return; } int i = exp.lastIndexOf('{', j); String a = exp.substring(0, i); String c = exp.substring(j + 1); for (String b : exp.substring(i + 1, j).split(",")) { dfs(a + b + c); } }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.