The Brace Expansion problem asks you to expand a given string expression that contains braces {} and commas , into all possible words, following specific rules. The input string can contain lowercase letters, braces denoting groups of options, and commas separating the options within a group. The expansion should return all possible unique words in lexicographical order.
For example, given the input "{a,b}c{d,e}f", you must generate all valid combinations by choosing one element from each group and concatenating them, resulting in ["acdf", "acef", "bcdf", "bcef"].
When first approaching this problem, it's tempting to try to generate all possible combinations by brute force, especially if you treat each group as a set of options and try every possible path. However, as the number of groups and options grows (especially with nesting), this approach quickly becomes inefficient and hard to manage.
Instead, it's helpful to think recursively: every time you encounter a group (inside braces), you can expand it into all its options, and then combine those options with the expansions of the rest of the string. This leads to a divide-and-conquer strategy, where you break the problem into smaller subproblems (expanding sub-expressions) and combine their results.
The challenge is correctly handling nested braces and concatenations, and ensuring that the options are combined in the right order. A stack or recursion can help keep track of the current context as you parse through the string.
To solve the Brace Expansion problem, we use a recursive parsing approach that handles nested braces and concatenations. Here is how the algorithm works:
{, we recursively parse the contents inside the braces, splitting options by commas at the current brace depth.This approach is both systematic and robust, handling all levels of nesting and ensuring that each expansion is valid.
Let's walk through the input "{a,b}c{d,e}f":
{a,b}, which expands to ["a", "b"].c, which is a fixed character, so it stays as is.{d,e}, which expands to ["d", "e"].f, which is also fixed.["a", "b"]["c"]["d", "e"]["f"]a + c + d + f = acdfa + c + e + f = acefb + c + d + f = bcdfb + c + e + f = bcef["acdf", "acef", "bcdf", "bcef"].
Brute-force Approach:
If we tried every possible combination without any pruning or optimization, the time complexity would be exponential in the number of groups and options, specifically O(k^n), where k is the average number of options per group and n is the number of groups.
Optimized Recursive Approach:
The optimized approach also has exponential complexity in the worst case, as we must generate every possible combination. However, the recursion and cartesian product are efficient for parsing and combining the results. The time complexity is O(k^n * m), where m is the average length of the resulting strings.
Space Complexity:
The space required is proportional to the number of unique expansions generated, which is also O(k^n * m).
The Brace Expansion problem is a classic recursive parsing task that requires careful handling of nested structures and concatenations. By breaking the problem into smaller parts, expanding each recursively, and combining the results, we can systematically generate all valid expansions. Using sets and sorting ensures uniqueness and correct order. The elegance of the solution lies in its recursive structure and its ability to naturally handle any level of nesting or complexity.
from typing import List
class Solution:
def expand(self, S: str) -> List[str]:
def helper(s):
res = []
i = 0
while i < len(s):
if s[i] == '{':
# find the matching }
j = i
count = 0
while j < len(s):
if s[j] == '{':
count += 1
elif s[j] == '}':
count -= 1
if count == 0:
break
j += 1
# split options by commas at this level
options = []
option = ''
brace_depth = 0
for k in range(i+1, j):
if s[k] == ',' and brace_depth == 0:
options.append(option)
option = ''
else:
if s[k] == '{':
brace_depth += 1
elif s[k] == '}':
brace_depth -= 1
option += s[k]
options.append(option)
# recursively expand each option
expanded = []
for opt in options:
expanded.extend(helper(opt))
if not res:
res = expanded
else:
res = [a + b for a in res for b in expanded]
i = j + 1
else:
j = i
while j < len(s) and s[j] != '{':
j += 1
part = s[i:j]
if not res:
res = [part]
else:
res = [a + part for a in res]
i = j
return res
return sorted(set(helper(S)))
#include <vector>
#include <string>
#include <set>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<string> expand(string S) {
vector<string> helper(string s) {
vector<string> res;
int i = 0;
while (i < s.size()) {
if (s[i] == '{') {
int j = i, count = 0;
while (j < s.size()) {
if (s[j] == '{') count++;
else if (s[j] == '}') {
count--;
if (count == 0) break;
}
j++;
}
vector<string> options;
string option = "";
int brace_depth = 0;
for (int k = i+1; k < j; ++k) {
if (s[k] == ',' && brace_depth == 0) {
options.push_back(option);
option = "";
} else {
if (s[k] == '{') brace_depth++;
else if (s[k] == '}') brace_depth--;
option += s[k];
}
}
options.push_back(option);
vector<string> expanded;
for (auto &opt : options) {
vector<string> exp = helper(opt);
expanded.insert(expanded.end(), exp.begin(), exp.end());
}
if (res.empty()) {
res = expanded;
} else {
vector<string> tmp;
for (auto &a : res)
for (auto &b : expanded)
tmp.push_back(a + b);
res = tmp;
}
i = j + 1;
} else {
int j = i;
while (j < s.size() && s[j] != '{') j++;
string part = s.substr(i, j-i);
if (res.empty()) {
res.push_back(part);
} else {
for (auto &a : res)
a += part;
}
i = j;
}
}
return res;
}
set<string> result(helper(S).begin(), helper(S).end());
vector<string> ans(result.begin(), result.end());
sort(ans.begin(), ans.end());
return ans;
}
};
import java.util.*;
class Solution {
public List<String> expand(String S) {
List<String> helper(String s) {
List<String> res = new ArrayList<>();
int i = 0;
while (i < s.length()) {
if (s.charAt(i) == '{') {
int j = i, count = 0;
while (j < s.length()) {
if (s.charAt(j) == '{') count++;
else if (s.charAt(j) == '}') {
count--;
if (count == 0) break;
}
j++;
}
List<String> options = new ArrayList<>();
StringBuilder option = new StringBuilder();
int braceDepth = 0;
for (int k = i+1; k < j; ++k) {
char c = s.charAt(k);
if (c == ',' && braceDepth == 0) {
options.add(option.toString());
option = new StringBuilder();
} else {
if (c == '{') braceDepth++;
else if (c == '}') braceDepth--;
option.append(c);
}
}
options.add(option.toString());
List<String> expanded = new ArrayList<>();
for (String opt : options) {
expanded.addAll(helper(opt));
}
if (res.isEmpty()) {
res = expanded;
} else {
List<String> tmp = new ArrayList<>();
for (String a : res)
for (String b : expanded)
tmp.add(a + b);
res = tmp;
}
i = j + 1;
} else {
int j = i;
while (j < s.length() && s.charAt(j) != '{') j++;
String part = s.substring(i, j);
if (res.isEmpty()) {
res.add(part);
} else {
for (int idx = 0; idx < res.size(); ++idx) {
res.set(idx, res.get(idx) + part);
}
}
i = j;
}
}
return res;
}
Set<String> result = new HashSet<>(helper(S));
List<String> ans = new ArrayList<>(result);
Collections.sort(ans);
return ans;
}
}
/**
* @param {string} S
* @return {string[]}
*/
var expand = function(S) {
function helper(s) {
let res = [];
let i = 0;
while (i < s.length) {
if (s[i] === '{') {
let j = i, count = 0;
while (j < s.length) {
if (s[j] === '{') count++;
else if (s[j] === '}') {
count--;
if (count === 0) break;
}
j++;
}
let options = [];
let option = '';
let braceDepth = 0;
for (let k = i+1; k < j; ++k) {
if (s[k] === ',' && braceDepth === 0) {
options.push(option);
option = '';
} else {
if (s[k] === '{') braceDepth++;
else if (s[k] === '}') braceDepth--;
option += s[k];
}
}
options.push(option);
let expanded = [];
for (let opt of options) {
expanded = expanded.concat(helper(opt));
}
if (res.length === 0) {
res = expanded;
} else {
let tmp = [];
for (let a of res)
for (let b of expanded)
tmp.push(a + b);
res = tmp;
}
i = j + 1;
} else {
let j = i;
while (j < s.length && s[j] !== '{') j++;
let part = s.slice(i, j);
if (res.length === 0) {
res = [part];
} else {
for (let idx = 0; idx < res.length; ++idx) {
res[idx] += part;
}
}
i = j;
}
}
return res;
}
let result = Array.from(new Set(helper(S)));
result.sort();
return result;
};