A comma-separated expression inside curly braces expands to a list of words.
If there is a prefix before the { or a suffix after the }, they also appear in each expansion.
Examples:
/2022/{jan,feb,mar}/report
→ /2022/jan/report
→ /2022/feb/report
→ /2022/mar/report
over{crowded,eager,ripe,tired}ness
→ overcrowdedness
→ overeagerness
→ overripeness
→ overtiredness
readme.txt{,.bak}
→ readme.txt
→ readme.txt.bak
Write a brace_expand function that takes a single pattern string and returns a list of expanded strings.
If the pattern is not expandable, return the original input as a one-element list.
Expand only when there are valid braces surrounding two or more tokens.
Examples:
pre{mat,ss}ure
→ premature
→ pressure
pre{mid}suf
→ pre{mid}suf (not expanded)
Invalid braces should also return the original input unchanged:
hello-{world
→ hello-{world
Finally, handle multiple nested brace expressions:
/20{19,20}/{jan,feb,mar}/
→ /2019/jan/
→ /2019/feb/
→ /2019/mar/
→ /2020/jan/
→ /2020/feb/
→ /2020/mar/
pre{A,B,C}mid{X,Y}suf
→ preAmidXsuf
→ preAmidYsuf
→ preBmidXsuf
→ preBmidYsuf
→ preCmidXsuf
→ preCmidYsuf
{A,B}{1,2}{x,y}{P,Q}
→ A1xP, A1xQ, A1yP, A1yQ, A2xP, A2xQ, A2yP, A2yQ, B1xP, ...
The brace_expand function should recursively process all valid brace patterns and generate all possible expansions, similar to how Bash shell handles brace expressions.
This problem focuses on implementing a brace expansion algorithm similar to the one used in Bash shell.
Given a string pattern containing comma-separated tokens inside curly braces, the task is to generate all possible expanded strings while preserving prefixes and suffixes.
It tests a candidate’s ability to handle recursive string parsing, cartesian product generation, and edge-case validation (such as unmatched or single-token braces).
Properly designed, the solution should support multiple and nested brace groups, ensuring all combinations are produced in correct order — a strong demonstration of parsing logic and recursion mastery.
The VOprep team has long accompanied candidates through various major company OAs and VOs, including Stripe, Google, Amazon, Citadel, SIG, providing real-time voice assistance, remote practice, and interview pacing reminders to help you stay smooth during critical moments. If you are preparing for Stripe or similar engineering-focused companies, you can check out our customized support plans—from coding interviews to system design, we offer full guidance to help you succeed.
