Given a string, perfrom the brace expansion .

For example,

Input: s = “a{d,c,b}e”

output: {ade , ace , abe}

Input: “a{b,c{d,e}}”

Output: [“ab”, “acd”, “ace”]

Input: “a{b,c,{d,e}}”

Output: [“ab”, “ac”, “ad”, “ae”]

Input : “ppp{,config,oe{,conf}}”

Output : [“ppp”, “pppconfig”, “pppoe”, “pppoeconf”]

can you share your approach?

rules :

- expansion of( {‘a’,‘b’} ) = {‘a’,‘b’}
- expansion of ( c{‘a’,‘b’} ) = {‘ca’,‘cb’}
- expansion of ( c{‘a’,‘b’}e{‘d’,‘f’} ) = (‘caed’,‘caef’,‘cbed’,‘cbef’)
- expansion of ( {‘a’,‘b’}{‘c’,‘d’} ) = {‘ac’,‘ad’,‘bc’,‘bd’ }