1096. Brace Expansion II - Leetcode Solution

Code Implementation

class Solution:
    def braceExpansionII(self, expression: str) -> List[str]:
        def parse(expr):
            stack = []
            cur = set([''])
            i = 0
            while i < len(expr):
                if expr[i] == '{':
                    count = 1
                    j = i + 1
                    while j < len(expr):
                        if expr[j] == '{':
                            count += 1
                        elif expr[j] == '}':
                            count -= 1
                        if count == 0:
                            break
                        j += 1
                    sub = parse(expr[i+1:j])
                    cur = set(a + b for a in cur for b in sub)
                    i = j
                elif expr[i] == ',':
                    stack.append(cur)
                    cur = set([''])
                else:
                    j = i
                    while j < len(expr) and expr[j].isalpha():
                        j += 1
                    token = expr[i:j]
                    cur = set(a + token for a in cur)
                    i = j - 1
                i += 1
            stack.append(cur)
            res = set()
            for s in stack:
                res |= s
            return res
        return sorted(parse(expression))

class Solution {
public:
    set<string> parse(const string& expr, int& i) {
        set<string> cur{""};
        vector<set<string>> stack;
        while (i < expr.size() && expr[i] != '}') {
            if (expr[i] == '{') {
                ++i;
                set<string> sub = parse(expr, i);
                set<string> tmp;
                for (const string& a : cur)
                    for (const string& b : sub)
                        tmp.insert(a + b);
                cur = tmp;
            } else if (expr[i] == ',') {
                stack.push_back(cur);
                cur = {""};
            } else if (isalpha(expr[i])) {
                int j = i;
                while (j < expr.size() && isalpha(expr[j])) ++j;
                string token = expr.substr(i, j - i);
                set<string> tmp;
                for (const string& a : cur)
                    tmp.insert(a + token);
                cur = tmp;
                i = j - 1;
            }
            ++i;
        }
        stack.push_back(cur);
        set<string> res;
        for (const auto& s : stack)
            res.insert(s.begin(), s.end());
        return res;
    }

    vector<string> braceExpansionII(string expression) {
        int i = 0;
        set<string> res = parse(expression, i);
        return vector<string>(res.begin(), res.end());
    }
};

class Solution {
    public List<String> braceExpansionII(String expression) {
        Set<String> res = parse(expression, new int[]{0});
        List<String> ans = new ArrayList<>(res);
        Collections.sort(ans);
        return ans;
    }
    private Set<String> parse(String expr, int[] i) {
        Set<String> cur = new HashSet<>();
        cur.add("");
        List<Set<String>> stack = new ArrayList<>();
        while (i[0] < expr.length() && expr.charAt(i[0]) != '}') {
            if (expr.charAt(i[0]) == '{') {
                i[0]++;
                Set<String> sub = parse(expr, i);
                Set<String> tmp = new HashSet<>();
                for (String a : cur)
                    for (String b : sub)
                        tmp.add(a + b);
                cur = tmp;
            } else if (expr.charAt(i[0]) == ',') {
                stack.add(cur);
                cur = new HashSet<>();
                cur.add("");
            } else if (Character.isLetter(expr.charAt(i[0]))) {
                int j = i[0];
                while (j < expr.length() && Character.isLetter(expr.charAt(j))) j++;
                String token = expr.substring(i[0], j);
                Set<String> tmp = new HashSet<>();
                for (String a : cur)
                    tmp.add(a + token);
                cur = tmp;
                i[0] = j - 1;
            }
            i[0]++;
        }
        stack.add(cur);
        Set<String> res = new HashSet<>();
        for (Set<String> s : stack)
            res.addAll(s);
        return res;
    }
}

var braceExpansionII = function(expression) {
    function parse(expr, i) {
        let cur = new Set(['']);
        let stack = [];
        while (i[0] < expr.length && expr[i[0]] !== '}') {
            if (expr[i[0]] === '{') {
                i[0]++;
                let sub = parse(expr, i);
                let tmp = new Set();
                for (let a of cur)
                    for (let b of sub)
                        tmp.add(a + b);
                cur = tmp;
            } else if (expr[i[0]] === ',') {
                stack.push(cur);
                cur = new Set(['']);
            } else if (/[a-z]/.test(expr[i[0]])) {
                let j = i[0];
                while (j < expr.length && /[a-z]/.test(expr[j])) j++;
                let token = expr.slice(i[0], j);
                let tmp = new Set();
                for (let a of cur)
                    tmp.add(a + token);
                cur = tmp;
                i[0] = j - 1;
            }
            i[0]++;
        }
        stack.push(cur);
        let res = new Set();
        for (let s of stack)
            for (let v of s)
                res.add(v);
        return res;
    }
    let i = [0];
    let res = parse(expression, i);
    return Array.from(res).sort();
};

Problem Description

Given a string expression representing a brace expansion (like in Bash shells), return all possible strings that the expression can generate, sorted in lexicographical order. The expression may contain lowercase letters, commas, and curly braces.

Commas (,) denote a union ("or") operation.
Concatenation is implicit (e.g., a{b,c} means ab or ac).
Curly braces can be nested arbitrarily deep.
All generated strings must be unique and sorted.

Constraints:

1 ≤ expression.length ≤ 50
expression consists of lowercase letters, '{', '}', and ','
There are no invalid expressions (all braces are balanced, etc.)

Thought Process

At first glance, this problem resembles parsing and evaluating mathematical expressions, but with sets of strings and two main operations: union (via commas) and concatenation (implicit). A brute-force approach might attempt to generate all possible substrings by recursively expanding every brace, but this quickly becomes inefficient with nested braces and repeated sub-expressions.

To optimize, we need to:

Recognize the recursive structure: each brace pair defines a sub-problem.
Use sets to avoid duplicates automatically.
Handle concatenation and union correctly, especially when nested.
Parse the string efficiently, managing the current position and nested levels.

The key insight is to treat the parsing as a recursive-descent process, building up sets of results at each step, and combining them as dictated by the grammar of the expression.

Solution Approach

Let's break down the solution into clear steps:

Recursive Parsing:
- Write a function that parses an expression from a starting index.
- Whenever a '{' is encountered, recursively parse the substring inside the braces.
- Whenever a ',' is encountered, treat it as a set union: collect the current set, and start a new one.
- Whenever a letter is encountered, add it to every string in the current set (concatenation).
Combining Results:
- Use sets to store unique strings at each stage.
- For concatenation, compute the Cartesian product of the current set and the next token or sub-expression.
- For union, merge sets as you parse through commas.
Managing State:
- Keep track of the current position in the string (using an index or pointer).
- When a closing brace '}' is found, return the set built so far to the previous recursion level.
Final Output:
- Convert the resulting set of strings to a sorted list before returning.

This approach ensures that we efficiently build all possible expansions, avoid duplicates, and handle arbitrary levels of nesting.

Example Walkthrough

Let's use the input expression = "{a,b}{c,{d,e}}".

First, parse {a,b} to get the set {"a", "b"}.
Next, parse {c,{d,e}}:
- Inside, c is a string, and {d,e} expands to {"d", "e"}.
- So, {c,{d,e}} becomes {"c", "d", "e"}.
These two sets are concatenated (Cartesian product):
- "a" + "c" = "ac"
- "a" + "d" = "ad"
- "a" + "e" = "ae"
- "b" + "c" = "bc"
- "b" + "d" = "bd"
- "b" + "e" = "be"
Final result: ["ac", "ad", "ae", "bc", "bd", "be"] (sorted).

This step-by-step process shows how the recursive parser combines union and concatenation to generate all valid strings.

Time and Space Complexity

Brute-force approach: If we simply tried every possible way to expand the expression, the time complexity would be exponential in the number of braces and options (i.e., O(2^N) where N is the number of options and nesting).

Optimized recursive approach:

Each unique sub-expression is parsed only once per recursion path.
Using sets ensures we do not generate duplicate strings.
The worst-case time and space complexity is still exponential (O(2^N)), as the number of unique expansions can be exponential in the size of the expression.
However, the use of sets and careful parsing ensures no unnecessary recomputation or duplicate storage.

Summary

The brace expansion problem is a classic example of recursive parsing and set manipulation. By treating the expression as a grammar with union and concatenation, and by using sets to manage uniqueness, we can efficiently generate all possible expansions, even for deeply nested expressions. The recursive-descent parser breaks the problem into manageable subproblems, and the use of sets and sorting ensures the final output meets the problem's requirements. This approach is robust, elegant, and leverages fundamental programming concepts.

AlgoMap.io

Want Help Cracking FAANG?