Brace Expansion I
A pattern describes a set of strings: a brace group {a,b} means "one of these characters", and everything else is a literal. Groups don't nest, and commas only appear inside groups. Return all strings the pattern can produce, sorted and without duplicates.
"{a,b}c{d,e}f" -> ["acdf", "acef", "bcdf", "bcef"]
"abcd" -> ["abcd"]Hints
Hint 1
Split the pattern into groups: each brace group becomes its sorted, deduplicated options, and each literal becomes a one-item group.
Hint 2
Build the cartesian product left to right: every prefix so far times every option of the next group.