# LeetCode 1087. Brace Expansion

## 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.