Brace Expansion II
Problem
Under a grammar, a string represents a set of lowercase words: a literal is a single-letter set, comma-separated parts inside braces form a union, and adjacent parts (juxtaposition) form a Cartesian concatenation. Return the sorted set of expanded words.
expression = "{a,b}{c,{d,e}}"["ac","ad","ae","bc","bd","be"]def brace_expansion_ii(expression):
groups = [[]] # union groups; current group is groups[-1]
stack = [] # saved (groups) at each '{'
i, n = 0, len(expression)
while i < n:
c = expression[i]
if c == '{':
stack.append(groups)
groups = [[]]
elif c == '}':
cur = union(groups)
groups = stack.pop()
groups[-1] = concat(groups[-1], cur)
elif c == ',':
groups.append([])
else:
groups[-1] = concat(groups[-1], [c])
i += 1
return sorted(union(groups))function braceExpansionII(expression) {
let groups = [[]];
const stack = [];
for (const c of expression) {
if (c === '{') { stack.push(groups); groups = [[]]; }
else if (c === '}') {
const cur = union(groups);
groups = stack.pop();
groups[groups.length-1] = concat(groups[groups.length-1], cur);
} else if (c === ',') {
groups.push([]);
} else {
groups[groups.length-1] = concat(groups[groups.length-1], [c]);
}
}
return [...new Set(union(groups))].sort();
}class Solution {
public List<String> braceExpansionII(String expression) {
Deque<List<Set<String>>> stack = new ArrayDeque<>();
List<Set<String>> groups = new ArrayList<>();
groups.add(new HashSet<>(Arrays.asList("")));
for (char c : expression.toCharArray()) {
if (c == '{') { stack.push(groups); groups = new ArrayList<>(); groups.add(new HashSet<>(Arrays.asList(""))); }
else if (c == '}') { Set<String> cur = union(groups); groups = stack.pop(); groups.set(groups.size()-1, concat(groups.get(groups.size()-1), cur)); }
else if (c == ',') { groups.add(new HashSet<>(Arrays.asList(""))); }
else { groups.set(groups.size()-1, concat(groups.get(groups.size()-1), new HashSet<>(Arrays.asList(String.valueOf(c))))); }
}
return new ArrayList<>(new TreeSet<>(union(groups)));
}
}vector<string> braceExpansionII(string expression) {
vector<vector<set<string>>> stack;
vector<set<string>> groups = {{""}};
for (char c : expression) {
if (c == '{') { stack.push_back(groups); groups = {{""}}; }
else if (c == '}') { auto cur = unionSets(groups); groups = stack.back(); stack.pop_back(); groups.back() = concat(groups.back(), cur); }
else if (c == ',') { groups.push_back({""}); }
else { groups.back() = concat(groups.back(), {string(1,c)}); }
}
auto u = unionSets(groups);
return vector<string>(u.begin(), u.end());
}Explanation
This grammar has two operations: commas mean union (a choice between options) and juxtaposition means concatenation (a Cartesian product of strings). Braces just group things. We handle the nesting with a stack of sets.
We keep groups, a list of pieces that get concatenated together; the current piece is groups[-1]. A literal letter c is concatenated into the current piece. A comma starts a brand-new branch by appending a fresh empty group.
When we see '{', we push the whole current groups onto the stack and start fresh inside the brace. When we see '}', we union everything we built inside, pop the saved outer groups, and concat that inner union onto the outer piece.
Example: "{a,b}{c,{d,e}}". The first brace gives the set {a,b}; the second gives {c,d,e}; since they sit side by side, we concatenate every pair, producing ac, ad, ae, bc, bd, be.
At the very end we union the final groups and sort to return the words in order.