Brace Expansion
Brace Expansion is a medium recursion & backtracking problem solved with the choice per position pattern.
The best approach, optimal (sorted groups + backtracking), runs in O(W · L) time and O(L) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from expand then sort up.
Problem
You are given a string s that describes a set of words. A plain lowercase letter stands for itself. A group in braces, such as {a,b,c}, stands for one of the listed letters. Groups are never nested.
Every word is formed by reading s left to right and picking one letter from each group. For example, "{p,q}r" describes "pr" and "qr".
Return all the words described by s, sorted in lexicographic order.
Examples
Example 1
- Input
s = "x{c,a}y{q,p}"- Output
["xayp", "xayq", "xcyp", "xcyq"]- Why
- Two choices at position 2 and two at position 4 give 2 × 2 = 4 words, listed in sorted order.
Example 2
- Input
s = "{m,k,z}"- Output
["k", "m", "z"]- Why
- A single group just lists its letters, sorted.
Example 3
- Input
s = "tree"- Output
["tree"]- Why
- With no braces there is exactly one word: the string itself.
Constraints
1 <= s.length <= 50sconsists of lowercase letters,'{','}'and','.- Braces are never nested, every group has at least two distinct letters, and the input is well formed.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Expand then sort | O(W · L · log W) | O(W · L) |
| Optimal (sorted groups + backtracking) | O(W · L) | O(L) |
1Expand then sort
O(W · L · log W)W words of length L are built; sorting them compares strings of length L.O(W · L)The current and next lists of partial words.Scan the string and keep a list of partial words. A plain letter is appended to every partial word; a group multiplies the list by its letters. At the end, sort the list.
- words = [""]; i = 0.
- If s[i] is '{', read letters up to '}' into opts; else opts = [s[i]].
- Replace words by every w + c for w in words and c in opts; move i past the token.
- Sort words and return them.
class Solution {
public List<String> expand(String s) {
List<String> words = new ArrayList<>();
words.add("");
int i = 0;
while (i < s.length()) {
List<Character> opts = new ArrayList<>();
if (s.charAt(i) == '{') {
i++;
while (s.charAt(i) != '}') {
if (s.charAt(i) != ',') opts.add(s.charAt(i));
i++;
}
} else {
opts.add(s.charAt(i));
}
i++;
List<String> next = new ArrayList<>();
for (String w : words) {
for (char c : opts) next.add(w + c);
}
words = next;
}
Collections.sort(words);
return words;
}
}class Solution:
def expand(self, s: str) -> List[str]:
words = [""]
i = 0
while i < len(s):
opts = []
if s[i] == '{':
i += 1
while s[i] != '}':
if s[i] != ',':
opts.append(s[i])
i += 1
else:
opts.append(s[i])
i += 1
words = [w + c for w in words for c in opts]
words.sort()
return wordsclass Solution {
public:
vector<string> expand(string s) {
vector<string> words = {""};
int i = 0, n = s.size();
while (i < n) {
vector<char> opts;
if (s[i] == '{') {
i++;
while (s[i] != '}') {
if (s[i] != ',') opts.push_back(s[i]);
i++;
}
} else {
opts.push_back(s[i]);
}
i++;
vector<string> next;
for (const string& w : words) {
for (char c : opts) next.push_back(w + c);
}
words = next;
}
sort(words.begin(), words.end());
return words;
}
};function expand(s) {
let words = [""];
let i = 0;
while (i < s.length) {
const opts = [];
if (s[i] === '{') {
i++;
while (s[i] !== '}') {
if (s[i] !== ',') opts.push(s[i]);
i++;
}
} else {
opts.push(s[i]);
}
i++;
const next = [];
for (const w of words) {
for (const c of opts) next.push(w + c);
}
words = next;
}
words.sort();
return words;
}2Optimal (sorted groups + backtracking)
O(W · L)Each of the W words is copied out once at length L; parsing and sorting the small groups is negligible.O(L)The buffer and the recursion depth are L, not counting the output.Parse the string once into positions, each holding its sorted allowed letters. Then backtrack with one shared character buffer: at position k try each letter in order and recurse. Because each position's letters are sorted and every word has the same length, words come out in lexicographic order, so no final sort is needed.
- Parse s into groups: a '{...}' block becomes its letters, a plain letter becomes a group of one. Sort each group.
- dfs(k): if k == number of groups, add the buffer as a word.
- Otherwise, for each letter c in groups[k] (ascending): buf[k] = c; dfs(k + 1).
- Call dfs(0) and return the collected words.
class Solution {
public List<String> expand(String s) {
List<char[]> groups = new ArrayList<>();
int i = 0;
while (i < s.length()) {
StringBuilder opts = new StringBuilder();
if (s.charAt(i) == '{') {
i++;
while (s.charAt(i) != '}') {
if (s.charAt(i) != ',') opts.append(s.charAt(i));
i++;
}
} else {
opts.append(s.charAt(i));
}
i++;
char[] g = opts.toString().toCharArray();
Arrays.sort(g);
groups.add(g);
}
List<String> res = new ArrayList<>();
dfs(groups, 0, new char[groups.size()], res);
return res;
}
private void dfs(List<char[]> groups, int k, char[] buf, List<String> res) {
if (k == groups.size()) {
res.add(new String(buf));
return;
}
for (char c : groups.get(k)) {
buf[k] = c;
dfs(groups, k + 1, buf, res);
}
}
}class Solution:
def expand(self, s: str) -> List[str]:
groups = []
i = 0
while i < len(s):
opts = []
if s[i] == '{':
i += 1
while s[i] != '}':
if s[i] != ',':
opts.append(s[i])
i += 1
else:
opts.append(s[i])
i += 1
groups.append(sorted(opts))
res = []
buf = [''] * len(groups)
def dfs(k: int) -> None:
if k == len(groups):
res.append("".join(buf))
return
for c in groups[k]:
buf[k] = c
dfs(k + 1)
dfs(0)
return resclass Solution {
vector<string> groups;
vector<string> res;
void dfs(int k, string& buf) {
if (k == (int) groups.size()) {
res.push_back(buf);
return;
}
for (char c : groups[k]) {
buf[k] = c;
dfs(k + 1, buf);
}
}
public:
vector<string> expand(string s) {
groups.clear();
res.clear();
int i = 0, n = s.size();
while (i < n) {
string opts;
if (s[i] == '{') {
i++;
while (s[i] != '}') {
if (s[i] != ',') opts.push_back(s[i]);
i++;
}
} else {
opts.push_back(s[i]);
}
i++;
sort(opts.begin(), opts.end());
groups.push_back(opts);
}
string buf(groups.size(), ' ');
dfs(0, buf);
return res;
}
};function expand(s) {
const groups = [];
let i = 0;
while (i < s.length) {
const opts = [];
if (s[i] === '{') {
i++;
while (s[i] !== '}') {
if (s[i] !== ',') opts.push(s[i]);
i++;
}
} else {
opts.push(s[i]);
}
i++;
groups.push(opts.sort());
}
const res = [];
const buf = new Array(groups.length);
const dfs = (k) => {
if (k === groups.length) {
res.push(buf.join(""));
return;
}
for (const c of groups[k]) {
buf[k] = c;
dfs(k + 1);
}
};
dfs(0);
return res;
}Edge cases to test
- No braces at all
- The whole string is one group
- Groups written out of order, like {z,a}
- Several groups next to each other with no fixed letters between them
Hints
Hint 1
Turn the string into a list of positions, where each position is a set of allowed letters (a fixed letter is a set of size one).
Hint 2
Every word picks one letter per position, which is a classic choose-one-per-slot backtracking.
Hint 3
Since every option is a single letter, sorting each position's letters makes the backtracking emit words already in sorted order.
FAQ
What is the best time complexity for Brace Expansion?
Optimal (sorted groups + backtracking) runs in O(W · L) time and O(L) extra space. Each of the W words is copied out once at length L; parsing and sorting the small groups is negligible.
Which pattern does Brace Expansion use?
It is a recursion & backtracking problem that uses the choice per position pattern. Other problems with the same pattern: Letter Combinations of a Phone Number, Confusing Number II, Strobogrammatic Number II.
Is there a brute force solution for Brace Expansion?
Yes. Expand then sort takes O(W · L · log W) time and O(W · L) space. Scan the string and keep a list of partial words.
Which edge cases should I test for Brace Expansion?
No braces at all; The whole string is one group; Groups written out of order, like {z,a}; Several groups next to each other with no fixed letters between them.