Looking for optimal solution...Brace Expansion

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 :

  1. expansion of( {‘a’,‘b’} ) = {‘a’,‘b’}
  2. expansion of ( c{‘a’,‘b’} ) = {‘ca’,‘cb’}
  3. expansion of ( c{‘a’,‘b’}e{‘d’,‘f’} ) = (‘caed’,‘caef’,‘cbed’,‘cbef’)
  4. expansion of ( {‘a’,‘b’}{‘c’,‘d’} ) = {‘ac’,‘ad’,‘bc’,‘bd’ }
1 Like

I don’t quite understand what you mean by the quality solution. In my opinion, it can be solved directly by DFS or BFS, I also think this is the lowest complexity for solving the problem.


Can you describe your approach?

I thought what I had sadi that was clear.

1 Like