Expand the Braces
pattern is made of lowercase letters, braces and commas, and stands for a set of words:
- Parts written one after another are joined.
- Braces hold one or more choices separated by commas, and stand for any one of them.
- A choice can hold braces of its own.
For example a{b,c{d,e}} stands for ab, acd and ace.
Return every different word pattern stands for, in any order.
Example 1
pattern "s{a,i}t"
returns ["sat","sit"]
The braces stand for a or i, between s and t.
Example 2
pattern "{b,c{a,o}}t"
returns ["bt","cat","cot"]
The outer braces stand for b, or for c followed by a or o. Then comes t.
Example 3
pattern "{a,a}b"
returns ["ab"]
Both choices are the same, so there is only one word.
Constraints
1 <= len(pattern) <= 40- the braces are balanced and no choice is empty
- commas appear only inside braces
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.