Brace Expansion II

Hard

#1039Time: 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.

Patterns

Backtracking

Algorithms

Breadth-First Search

Data structures

String Stack

Prompt

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 e₁, e₂, ... , e_k with k >= 2, we have R({e₁, e₂, ...}) = R(e₁) ∪ R(e₂) ∪ ...
For expressions e₁ and e₂, we have R(e₁ + e₂) = {a + b for (a, b) in R(e₁) × R(e₂)}, 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.

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 a List<String>.
Inside parseExpr(), create an empty list unionList.
Loop to parse terms separated by commas:
- Call a parseTerm() function to get a List<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.
Return unionList.
Implement parseTerm() which returns a List<String>.
Initialize productList with 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 productList and the factor's list, storing it in a new list.
- Replace productList with the new list.
Return productList.
Implement parseFactor() which returns a List<String>.
- If the character is {, consume it, recursively call parseExpr(), consume }, and return the result.
- If the character is a letter, read the entire word and return a list containing just that word.
In the main function, call parseExpr() on the whole expression.
Convert the resulting list to a HashSet to get unique words.
Convert the HashSet to an ArrayList and 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.

parseExpr handles comma-separated unions (the R({e1, e2, ...}) rule). It calls parseTerm for each expression part and combines the resulting lists of words.
parseTerm handles concatenation (the R(e1 + e2) rule). It calls parseFactor repeatedly for each concatenated element and computes the Cartesian product of the resulting lists.
parseFactor handles the base cases: single letters (or words) and nested expressions within curly braces ({...}). For nested expressions, it makes a recursive call to parseExpr to 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.

1import java.util.*;2 3class Solution {4    int pos = 0;5    String expression;6 7    public List<String> braceExpansionII(String expression) {8        this.expression = expression;9        this.pos = 0;10        List<String> resultList = parseExpr();11        // Deduplicate and sort12        Set<String> resultSet = new HashSet<>(resultList);13        List<String> sortedList = new ArrayList<>(resultSet);14        Collections.sort(sortedList);15        return sortedList;16    }17 18    // An expression is a comma-separated list of terms.19    private List<String> parseExpr() {20        List<String> unionList = new ArrayList<>();21        while (true) {22            unionList.addAll(parseTerm());23            if (pos < expression.length() && expression.charAt(pos) == ',') {24                pos++; // Consume ','25            } else {26                break;27            }28        }29        return unionList;30    }31 32    // A term is a concatenation of factors.33    private List<String> parseTerm() {34        List<String> productList = new ArrayList<>();35        productList.add(""); // Identity for concatenation36 37        while (pos < expression.length() && (Character.isLetter(expression.charAt(pos)) || expression.charAt(pos) == '{')) {38            List<String> factorList = parseFactor();39            List<String> newProductList = new ArrayList<>();40            for (String s1 : productList) {41                for (String s2 : factorList) {42                    newProductList.add(s1 + s2);43                }44            }45            productList = newProductList;46        }47        return productList;48    }49 50    // A factor is a single word or a nested expression.51    private List<String> parseFactor() {52        if (expression.charAt(pos) == '{') {53            pos++; // Consume '{'54            List<String> result = parseExpr();55            pos++; // Consume '}'56            return result;57        } else { // Letter58            StringBuilder sb = new StringBuilder();59            while (pos < expression.length() && Character.isLetter(expression.charAt(pos))) {60                sb.append(expression.charAt(pos));61                pos++;62            }63            List<String> result = new ArrayList<>();64            result.add(sb.toString());65            return result;66        }67    }68}

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.

This approach improves upon the previous one by using Set<String> instead of List<String> to store intermediate results. By using a TreeSet, we ensure that the collections of words are always unique and sorted. This eliminates the need for a final deduplication and sorting step and prevents the explosive growth of intermediate collections with duplicate entries, making it significantly more efficient.

Algorithm

Implement a recursive function parseExpr() that returns a TreeSet<String>.
Inside parseExpr(), create an empty TreeSet, unionSet.
Loop to parse terms separated by commas:
- Call a parseTerm() function to get a TreeSet<String> for the current term.
- Add all elements from the term's set to unionSet using addAll.
- If the next character is a comma, consume it and continue. Otherwise, break.
Return unionSet.
Implement parseTerm() which returns a TreeSet<String>.
Initialize productSet with a TreeSet containing one empty string.
Loop as long as the next part of the expression is a factor:
- Call parseFactor() to get a TreeSet for the factor.
- Compute the Cartesian product of productSet and the factor's set, storing it in a new TreeSet.
- Replace productSet with the new set.
Return productSet.
Implement parseFactor() which returns a TreeSet<String>.
- If the character is {, consume it, recursively call parseExpr(), consume }, and return the result.
- If the character is a letter, read the word and return a TreeSet containing just that word.
In the main function, call parseExpr() on the whole expression.
Convert the resulting TreeSet to an ArrayList.

Walkthrough

The parsing logic remains a recursive descent parser with parseExpr, parseTerm, and parseFactor functions. The key difference is the choice of data structure.

Instead of List<String>, all functions now operate on and return Set<String>. Specifically, we use TreeSet which maintains its elements in sorted order. This has two major benefits:

Automatic Deduplication: When we add elements to a TreeSet, duplicates are automatically ignored. This keeps the size of our intermediate collections minimal.
Automatic Sorting: TreeSet keeps the strings sorted lexicographically. This means the final set of words is already sorted, and we just need to convert it to a list.

parseExpr (union) uses set.addAll() to efficiently merge two sorted sets.
parseTerm (concatenation) computes the Cartesian product, and the results are stored in a new TreeSet.

This approach is much more efficient in both time and space because it avoids the overhead of processing and storing duplicate strings.

1import java.util.*;2 3class Solution {4    int pos = 0;5    String expression;6 7    public List<String> braceExpansionII(String expression) {8        this.expression = expression;9        this.pos = 0;10        Set<String> resultSet = parseExpr();11        return new ArrayList<>(resultSet);12    }13 14    // An expression is a comma-separated list of terms.15    private Set<String> parseExpr() {16        Set<String> unionSet = new TreeSet<>();17        while (true) {18            unionSet.addAll(parseTerm());19            if (pos < expression.length() && expression.charAt(pos) == ',') {20                pos++; // Consume ','21            } else {22                break;23            }24        }25        return unionSet;26    }27 28    // A term is a concatenation of factors.29    private Set<String> parseTerm() {30        Set<String> productSet = new TreeSet<>();31        productSet.add(""); // Identity for concatenation32 33        while (pos < expression.length() && (Character.isLetter(expression.charAt(pos)) || expression.charAt(pos) == '{')) {34            Set<String> factorSet = parseFactor();35            Set<String> newProductSet = new TreeSet<>();36            for (String s1 : productSet) {37                for (String s2 : factorSet) {38                    newProductSet.add(s1 + s2);39                }40            }41            productSet = newProductSet;42        }43        return productSet;44    }45 46    // A factor is a single word or a nested expression.47    private Set<String> parseFactor() {48        if (expression.charAt(pos) == '{') {49            pos++; // Consume '{'50            Set<String> result = parseExpr();51            pos++; // Consume '}'52            return result;53        } else { // Letter54            Set<String> result = new TreeSet<>();55            StringBuilder sb = new StringBuilder();56            while (pos < expression.length() && Character.isLetter(expression.charAt(pos))) {57                sb.append(expression.charAt(pos));58                pos++;59            }60            result.add(sb.toString());61            return result;62        }63    }64}

Complexity

Time

O(N + TotalChars * log S), where `N` is the expression length, `TotalChars` is the sum of lengths of all generated unique strings (intermediate and final), and `S` is the maximum size of any set. The `log S` factor comes from `TreeSet` insertions. This is highly efficient and its performance is tied to the size of the actual output.

Space

O(N + C), where `N` is the expression length and `C` is the total number of characters in all unique final words. This is optimal as we must store the result.

Trade-offs

Pros

Highly efficient as duplicates are pruned early, preventing intermediate data structures from bloating.
TreeSet automatically keeps the words sorted, simplifying the final step.
The code is cleaner as it doesn't need a separate deduplication/sorting phase.

Cons

TreeSet operations (add, addAll) have a logarithmic time complexity factor (log K, where K is the set size), which might be slightly slower than HashSet for very large sets, but the benefit of sorted output and early duplicate removal generally outweighs this minor overhead.

Solutions

Solution

1class Solution {2private3  TreeSet<String> s = new TreeSet<>();4public5  List<String> braceExpansionII(String expression) {6    dfs(expression);7    return new ArrayList<>(s);8  }9private10  void dfs(String exp) {11    int j = exp.indexOf('}');12    if (j == -1) {13      s.add(exp);14      return;15    }16    int i = exp.lastIndexOf('{', j);17    String a = exp.substring(0, i);18    String c = exp.substring(j + 1);19    for (String b : exp.substring(i + 1, j).split(",")) {20      dfs(a + b + c);21    }22  }23}

1class Solution {2public:3  vector<string> braceExpansionII(string expression) {4    dfs(expression);5    return vector<string>(s.begin(), s.end());6  }7 8private:9  set<string> s;10  void dfs(string exp) {11    int j = exp.find_first_of('}');12    if (j == string ::npos) {13      s.insert(exp);14      return;15    }16    int i = exp.rfind('{', j);17    string a = exp.substr(0, i);18    string c = exp.substr(j + 1);19    stringstream ss(exp.substr(i + 1, j - i - 1));20    string b;21    while (getline(ss, b, ',')) {22      dfs(a + b + c);23    }24  }25};

1class Solution:2    def braceExpansionII(self, expression: str) -> List[str]: def dfs(exp): j = exp . find('}') if j == - 1: s . add(exp) return i = exp . rfind('{', 0, j - 1) a, c = exp[: i], exp[j + 1:] for b in exp[i + 1: j]. split(','): dfs(a + b + c) s = set() dfs(expression) return sorted(s)

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.

← Previous

Previous problem

Next problem