1087. Brace Expansion
Asked at Anduril
Difficulty
Medium
Time
O(L * P)
Space
O(L * P)
Pattern
String
Companies
1
Problem
You are given a pattern string s. It describes a set of words. A plain lowercase letter in s means that letter appears in every word. A group written as {a,b,c} means the word takes exactly one of those letters at that position.
For example, "a{b,c}" produces the words "ab" and "ac". The a is fixed, and the brace group offers two choices.
Return all words the pattern can produce, sorted in lexicographical order. There is no nesting: a brace group never sits inside another brace group.
One letter chosen from each group
Constraints
- ●
1 <= s.length <= 50 - ●
s contains only curly brackets '{}', commas ',', and lowercase English letters - ●
s is guaranteed to be a valid input - ●
There are no nested curly brackets - ●
All characters inside one pair of braces are different
Examples
s = "{a,b}c{d,e}f"["acdf","acef","bcdf","bcef"]s = "abcd"["abcd"]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Anduril | Medium | View all Anduril questions → |
How to Think About It
Parse first: turn the string into a list of groups, where a plain letter is a group of size 1 and {x,y,z} is a group of three options.
The result is the Cartesian product of the groups. Build it with backtracking (choose one option per group) or iteratively (extend every partial word with each option).
Sort each group before expanding. Then backtracking generates words in lexicographic order automatically — no final sort needed.
Walkthrough for "{a,b}c{d,e}f": groups [a,b] [c] [d,e] [f] -> acdf, acef, bcdf, bcef.
The output can have up to the product of group sizes entries, so complexity is dominated by output size.
Optimal Approach
Step 1: Parse into groups: on {, read letters until } (skip commas) and sort them; otherwise the single letter is a group.
Step 2: res = [""].
Step 3: For each group, res = [w + c for w in res for c in group].
Step 4: Return res (already sorted because groups are sorted and processed in order).
Time: O(L * P) where P is the number of words and L their length. Space: O(L * P).
Parse, then extend word by word
What Trips People Up in Real Interviews
Forgetting to sort the output. Sorting each group up front is the cheap way to get it for free.
Treating commas as characters in the result.
Using recursion with string slicing on the raw pattern at every step — parse once, then expand.
Assuming nested braces. This version has none; mention that Brace Expansion II handles nesting with a grammar.
Solution Code
O(L * P) timedef expand(s):
groups = []
i = 0
while i < len(s):
if s[i] == '{':
j = s.index('}', i)
groups.append(sorted(s[i + 1:j].split(',')))
i = j + 1
else:
groups.append([s[i]])
i += 1
res = ['']
for g in groups:
res = [w + c for w in res for c in g]
return resFrequently Asked Questions
What is the Brace Expansion problem?
Brace Expansion takes a pattern like `"{a,b}c{d,e}f"`, where each brace group lists alternative letters, and asks for every word it can produce, sorted lexicographically. There is no nesting, so parse the pattern into a list of option groups and take their Cartesian product.
How do you solve Brace Expansion?
The optimal approach runs in O(L * P) time and O(L * P) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Brace Expansion?
Brace Expansion is asked at Anduril. It is a medium difficulty problem.
What are common mistakes on Brace Expansion?
- Forgetting to sort the output. Sorting each group up front is the cheap way to get it for free.
- Treating commas as characters in the result.
- Using recursion with string slicing on the raw pattern at every step — parse once, then expand.
- Assuming nested braces. This version has none; mention that Brace Expansion II handles nesting with a grammar.