# Brace Expansion II
**Difficulty:** HARD
[External](https://leetcode.com/problems/brace-expansion-ii)
Canonical: https://scaleengineer.com/dsa/problems/brace-expansion-ii
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** String, Stack
---
## Problem
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.

# Approaches
## Recursive Descent with Lists and Final Deduplication
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.
**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.
**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.
### Explanation
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.

```java
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;
        }
    }
}
```
### 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.

## Optimized Recursive Descent with Sets
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.
**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.
**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.
### Explanation
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:
1.  **Automatic Deduplication**: When we add elements to a `TreeSet`, duplicates are automatically ignored. This keeps the size of our intermediate collections minimal.
2.  **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.

```java
import java.util.*;

class Solution {
    int pos = 0;
    String expression;

    public List<String> braceExpansionII(String expression) {
        this.expression = expression;
        this.pos = 0;
        Set<String> resultSet = parseExpr();
        return new ArrayList<>(resultSet);
    }

    // An expression is a comma-separated list of terms.
    private Set<String> parseExpr() {
        Set<String> unionSet = new TreeSet<>();
        while (true) {
            unionSet.addAll(parseTerm());
            if (pos < expression.length() && expression.charAt(pos) == ',') {
                pos++; // Consume ','
            } else {
                break;
            }
        }
        return unionSet;
    }

    // A term is a concatenation of factors.
    private Set<String> parseTerm() {
        Set<String> productSet = new TreeSet<>();
        productSet.add(""); // Identity for concatenation

        while (pos < expression.length() && (Character.isLetter(expression.charAt(pos)) || expression.charAt(pos) == '{')) {
            Set<String> factorSet = parseFactor();
            Set<String> newProductSet = new TreeSet<>();
            for (String s1 : productSet) {
                for (String s2 : factorSet) {
                    newProductSet.add(s1 + s2);
                }
            }
            productSet = newProductSet;
        }
        return productSet;
    }

    // A factor is a single word or a nested expression.
    private Set<String> parseFactor() {
        if (expression.charAt(pos) == '{') {
            pos++; // Consume '{'
            Set<String> result = parseExpr();
            pos++; // Consume '}'
            return result;
        } else { // Letter
            Set<String> result = new TreeSet<>();
            StringBuilder sb = new StringBuilder();
            while (pos < expression.length() && Character.isLetter(expression.charAt(pos))) {
                sb.append(expression.charAt(pos));
                pos++;
            }
            result.add(sb.toString());
            return result;
        }
    }
}
```
### 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`.

# Solutions
### Java

```java
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);
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<string> braceExpansionII(string expression) {
    dfs(expression);
    return vector<string>(s.begin(), s.end());
  }

private:
  set<string> s;
  void dfs(string exp) {
    int j = exp.find_first_of('}');
    if (j == string ::npos) {
      s.insert(exp);
      return;
    }
    int i = exp.rfind('{', j);
    string a = exp.substr(0, i);
    string c = exp.substr(j + 1);
    stringstream ss(exp.substr(i + 1, j - i - 1));
    string b;
    while (getline(ss, b, ',')) {
      dfs(a + b + c);
    }
  }
};

```

### Python

```python
class Solution:
    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)

```