Brace Expansion II — Solution in Python, Java & C++
Brace Expansion II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Brace Expansion II is a hard coding problem on strings, breadth-first search and stack, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Strings, Breadth-First Search, Stack, Backtracking
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An expression describes a set of lowercase words. Write R(e) for the set that expression e stands for. The grammar has three rules:
- A single lowercase letter
xstands for the set with one word:R("a") = {"a"}. - A comma-separated list of two or more expressions inside braces stands for the union of their sets:
R("{a,b,c}") = {"a","b","c"}andR("{{a,b},{b,c}}") = {"a","b","c"}. - Two expressions written next to each other stand for every concatenation of a word from the first with a word from the second:
R("{a,b}{c,d}") = {"ac","ad","bc","bd"}andR("a{b,c}{d,e}f")has 4 words.
Given expression, return the words of R(expression) with no duplicates, in sorted (lexicographic) order.
Example 1
Input: expression = "{c,k}{o,{d,e}}"
Output: ["cd","ce","co","kd","ke","ko"]
Example 2
Input: expression = "{{a,b},a{x,y},{ab,z}}"
Output: ["a","ab","ax","ay","b","z"]
Explanation: Duplicates such as the second `a` disappear in the union.
Example 3
Input: expression = "k{ai,i}ro"
Output: ["kairo","kiro"]
Constraints
1 <= expression.length <= 60expression[i] is '{', '}', ',' or a lowercase English letterexpression follows the grammar above
Hints for Brace Expansion II
Hint 1
There are two operators: union (
,) and concatenation (adjacency). Concatenation binds tighter, like*over+.Hint 2
Parse with two mutually recursive functions: one reads a comma-separated union, the other reads a run of adjacent items, each item being a letter or a braced union.
Hint 3
Represent each partial result as a set of strings: union merges sets, concatenation forms the cartesian product. Sort the final set.
How to solve Brace Expansion II
The grammar is an expression language with two operators — union and concatenation — so a small recursive-descent parser that evaluates each sub-expression to a set of words solves it directly.
Approach
parseUnion: read one concatenation; while the next character is,, skip it and union in another concatenation.parseConcat: start with the set{""}. While the next character is neither,nor}nor the end: if it is{, skip it, read aparseUnion, and skip the}; otherwise take the single letter. Replace the accumulated set by the cartesian product with that item.- Evaluate the whole string with
parseUnion, then sort the words.
Why it works
parseConcat stops exactly at the characters that end a concatenation (, belongs to the enclosing union, } to the enclosing brace), so each function consumes precisely the text of the rule it implements, mirroring the grammar's precedence. Using sets at every level removes duplicates as soon as they arise, so the result is the set R(expression).
Complexity
- Time —
O(L · W) roughly, where W is the number of words produced (bounded by the 60-character input) - Space —
O(W · L)
Pitfalls
- Concatenation binds tighter than the comma:
{a,b}cinside braces is{a, bc}, not{ac, bc}. - Deduplicate — the same word can be produced by different branches.
- Sort the output; set iteration order is arbitrary in most languages.
Reference solution
Python
from typing import List
def braceExpansionII(expression: str) -> List[str]:
s = expression
pos = [0]
def parse_union():
result = set(parse_concat())
while pos[0] < len(s) and s[pos[0]] == ',':
pos[0] += 1
result |= parse_concat()
return result
def parse_concat():
result = {''}
while pos[0] < len(s) and s[pos[0]] not in ',}':
if s[pos[0]] == '{':
pos[0] += 1
part = parse_union()
pos[0] += 1
else:
part = {s[pos[0]]}
pos[0] += 1
result = {a + b for a in result for b in part}
return result
return sorted(parse_union())Java
private static String braceSrc;
private static int bracePos;
private static Set<String> braceUnionPart() {
Set<String> result = braceConcatPart();
while (bracePos < braceSrc.length() && braceSrc.charAt(bracePos) == ',') {
bracePos++;
result.addAll(braceConcatPart());
}
return result;
}
private static Set<String> braceConcatPart() {
Set<String> result = new HashSet<>();
result.add("");
while (bracePos < braceSrc.length() && braceSrc.charAt(bracePos) != ',' && braceSrc.charAt(bracePos) != '}') {
Set<String> part;
if (braceSrc.charAt(bracePos) == '{') {
bracePos++;
part = braceUnionPart();
bracePos++;
} else {
part = new HashSet<>();
part.add(String.valueOf(braceSrc.charAt(bracePos)));
bracePos++;
}
Set<String> next = new HashSet<>();
for (String a : result) for (String b : part) next.add(a + b);
result = next;
}
return result;
}
public static String[] braceExpansionII(String expression) {
braceSrc = expression;
bracePos = 0;
TreeSet<String> sorted = new TreeSet<>(braceUnionPart());
return sorted.toArray(new String[0]);
}C++
set<string> braceUnionPart(const string& s, int& pos);
set<string> braceConcatPart(const string& s, int& pos) {
set<string> result;
result.insert("");
while (pos < (int)s.size() && s[pos] != ',' && s[pos] != '}') {
set<string> part;
if (s[pos] == '{') {
pos++;
part = braceUnionPart(s, pos);
pos++;
} else {
part.insert(string(1, s[pos]));
pos++;
}
set<string> next;
for (const string& a : result)
for (const string& b : part) next.insert(a + b);
result = next;
}
return result;
}
set<string> braceUnionPart(const string& s, int& pos) {
set<string> result = braceConcatPart(s, pos);
while (pos < (int)s.size() && s[pos] == ',') {
pos++;
set<string> more = braceConcatPart(s, pos);
result.insert(more.begin(), more.end());
}
return result;
}
vector<string> braceExpansionII(string expression) {
int pos = 0;
set<string> all = braceUnionPart(expression, pos);
return vector<string>(all.begin(), all.end());
}JavaScript
var braceExpansionII = function(expression) {
var s = expression, pos = 0;
var parseUnion = function() {
var result = parseConcat();
while (pos < s.length && s[pos] === ",") {
pos++;
parseConcat().forEach(function(w) { result.add(w); });
}
return result;
};
var parseConcat = function() {
var result = new Set([""]);
while (pos < s.length && s[pos] !== "," && s[pos] !== "}") {
var part;
if (s[pos] === "{") {
pos++;
part = parseUnion();
pos++;
} else {
part = new Set([s[pos]]);
pos++;
}
var next = new Set();
result.forEach(function(a) {
part.forEach(function(b) { next.add(a + b); });
});
result = next;
}
return result;
};
return Array.from(parseUnion()).sort();
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Breadth-First Search (BFS)