## Description

https://leetcode.com/problems/brace-expansion/

You are given a string `s`

representing a list of words. Each letter in the word has one or more options.

- If there is one option, the letter is represented as is.
- If there is more than one option, then curly braces delimit the options. For example,
`"{a,b,c}"`

represents options`["a", "b", "c"]`

.

For example, if `s = "a{b,c}"`

, the first character is always `'a'`

, but the second character can be `'b'`

or `'c'`

. The original list is `["ab", "ac"]`

.

Return all words that can be formed in this manner, **sorted** in lexicographical order.

**Example 1:**

Input:s = "{a,b}c{d,e}f"Output:["acdf","acef","bcdf","bcef"]

**Example 2:**

Input:s = "abcd"Output:["abcd"]

**Constraints:**

`1 <= s.length <= 50`

`s`

consists of curly brackets`'{}'`

, commas`','`

, and lowercase English letters.`s`

is guaranteed to be a valid input.- There are no nested curly brackets.
- All characters inside a pair of consecutive opening and ending curly brackets are different.

## Explanation

The goal of the problem is to find all combination strings. Whenever we encounter a ‘{‘, we can build combinations from different options, after that, we go to the character after ‘}’ to continue building combinations. When we encounter a letter, we just go to the next character in the string. In the end, sort the results in alphabetically ascending order.

## Python Solution

```
class Solution:
def expand(self, s: str) -> List[str]:
results = []
end = len(s)
self.helper(results, "", 0, s)
results = sorted(results)
return results
def helper(self, results, combination, start, s):
if start == len(s):
results.append(combination)
return
i = start
if s[i] == '{':
j = i + 1
options = []
while s[j] != '}':
if s[j] != ',':
options.append(s[j])
j += 1
for option in options:
self.helper(results, combination + option, j + 1, s)
elif s[i] == '}':
return
else:
self.helper(results, combination + s[i], i + 1, s)
```

- Time Complexity: O(N).
- Space Complexity: O(N).

where Q is the length of queries and N is the length of colors.