Leetcode 1096. Brace Expansion II

Problem Explanation:

Given an expression string, we need to find all unique sets of words or letters it generates following certain grammatical rules. Here are the rules:

1. For every lowercase letter x, we have R(x) = {x}
2. For expressions {e_1, e_2, ... , e_k}, we have R({e_1,e_2,...}) = R(e_1) ∪ R(e_2) ∪ ...
3. For expressions {e_1,e_2}, we have R({e_1,e_2}) = {a + b for (a, b) in R(e_1) × R(e_2)}, where + denotes concatenation, and x denotes the cartesian product.

Example:

Let's take an example:

Input: "{a,b}{c,{d,e}}"

There are two groups ({a,b} and {c,{d,e}}). The first group gives a or b, and the second group gives c, d, or e. So, the possible combinations from each group would be: "ac", "ad", "ae", "bc", "bd", "be". Thus, the output is ["ac","ad","ae","bc","bd","be"].

Solution's Approach:

The solution uses the concept of Depth-First Search (DFS). Given an expression, it scans the expression from left to right inside a while loop. If it encounters opening braces, it will recursively call the DFS function with parameters as the start and end index within the braces. The function returns the data between the braces and adds it to a "groups" variable.

Each parenthesis expansion is a DFS problem where the point of backtracking is the comma ','. The merging operation is like the Cartesian Product: it strings together, in all combinations, all groups before and after a comma, or before the comma and the resolved group inside a pair of parentheses.

Solution in Python

1
2python
3class Solution:
4    def braceExpansionII(self, expression: str) -> List[str]:
5        groups = [[]]
6        level = []
7        for i, c in enumerate(expression):
8            if c == '{':
9                level.append(i)
10            elif c == '}':
11                start = level.pop()
12                if not level:
13                    groups[-1].append(self.braceExpansionII(expression[start + 1: i]))
14            elif c == ',' and not level:
15                groups.append([])
16            elif not level:
17                groups[-1].append([c])
18        
19        result = set()
20        for group in groups:
21            result |= set(map(''.join, itertools.product(*group)))
22        return sorted(result)

Here, we use a stack to store the level of nested braces. The python deque structure is very efficient for implementing stacks and queues when we require a frequently inserting and deleting elements.

In python, The * operator is used in the itertools.product() to get all combinations. The sorted() function returns a sorted list from the given iterable. And set() function returns a set from the given iterable.

Solution in Java

1
2java
3class Solution {
4    public List<String> braceExpansionII(String expression) {
5        Set<String> set = new HashSet<>();
6        List<Set<String>> stack = new ArrayList<>();
7        stack.add(set);
8        
9        for (char c : expression.toCharArray()) {
10            if ('a' <= c && c <= 'z') {
11                Set<String> newSet = new HashSet<>();
12                for (String prefix : stack.get(stack.size() - 1)) {
13                    newSet.add(prefix + c);
14                }
15                stack.set(stack.size() - 1, newSet);
16            } else if (c == '{') {
17                stack.add(new HashSet<>(Arrays.asList("")));
18            } else if (c == '}' || c == ',') {
19                Set<String> top = stack.remove(stack.size() - 1);
20                if (c == '}') {
21                    Set<String> newSet = new HashSet<>();
22                    for (String prefix : stack.get(stack.size() - 1)) {
23                        for (String word : top) {
24                            newSet.add(prefix + word);
25                        }
26                    }
27                    stack.set(stack.size() - 1, newSet);
28                } else {
29                    for (String word : top) {
30                        stack.get(stack.size() - 1).add(word);
31                    }
32                    stack.add(new HashSet<>(Arrays.asList("")));
33                }
34            }
35        }
36
37        List<String> ans = new ArrayList<>(stack.get(stack.size() - 1));
38        Collections.sort(ans);
39        return ans;
40    }
41}

In Java, The add() method appends the specified element to the end of this list and remove() method removes the last element.

The sort() method sorts the elements of the specified list in ascending order.

Note:

Please note that the problem does not specify the language of the solution or the preferred language. This makes it difficult to provide solutions in all specified languages. However, the two solutions provided are comprehensive and use wide-spread languages, Python and Java, for the answer.## Solution in JavaScript

In Javascript, consistent with the previous language solutions, we can accomplish the solution using stack, collection, and iterative logic in a functional style:

1
2javascript
3var braceExpansionII = function(expression) {
4    let stack = [[]];
5    let wordBuffer = [''];
6    let level = 0;
7
8    for (let i = 0, l = expression.length; i < l; i++) {
9        let c = expression.charAt(i);
10        if (isLowercaseAlphabet(c)) {
11            wordBuffer = product(wordBuffer, [c]);
12        } else if (c === '{') {
13            if (level++ > 0) wordBuffer.push(c);
14            stack.push(wordBuffer);
15            wordBuffer = [''];
16        } else if (c === '}') {
17            if (--level > 0) {
18                wordBuffer.push(c);
19            } else {
20                let words = stack.pop();
21                words[words.length - 1] = product(words[words.length - 1], union(wordBuffer));
22                wordBuffer = stack.pop();
23                wordBuffer[wordBuffer.length - 1] = product(wordBuffer[wordBuffer.length - 1], union(words));
24            }
25        } else if (c === ',') {
26            if (level > 0) {
27                wordBuffer.push(c);
28            } else {
29                stack[stack.length - 1].push(union(wordBuffer));
30                wordBuffer = [''];
31            }
32        }
33    }
34    return [...new Set(union(product(wordBuffer, stack.pop())))].sort();
35}
36
37function isLowercaseAlphabet(c) {
38    return c >= 'a' && c <= 'z';
39}
40
41function union(arr) {
42    return Array.isArray(arr) ? [].concat(...arr) : [arr];
43}
44
45function product(A, B) {
46    let ret = [];
47    for (let a of A)
48        for (let b of B)
49            ret.push(a + b);
50    return ret;
51}

In JavaScript, we used various helper methods to streamline our logic, such as isLowercaseAlphabet(c), union(arr), and product(A, B). Similar to the Python and Java solution, we maintained a stack and wordBuffer to hold our current groups and words.

The union() function is used to simplify data structures involved in a union operation, which could be an array of arrays or a string. In product(A, B), a new array is generated by taking all possible concatenated strings between any two elements in array A and B.

Note that by using Set, we ensure all the items are unique before sorting and returning it as the final answer. The Set object lets you store unique values of any type, whether primitive values or object references.