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

## Rust Solution

``````struct Solution;

impl Solution {
fn expand(s: String) -> Vec<String> {
let mut v: Vec<Vec<char>> = vec![];
let mut stack: Vec<char> = vec![];
let mut inbrace = false;
for c in s.chars() {
match c {
'{' => {
inbrace = true;
}
'}' => {
stack.sort_unstable();
v.push(stack);
stack = vec![];
inbrace = false;
}
',' => {}
_ => {
if inbrace {
stack.push(c);
} else {
v.push(vec![c]);
}
}
}
}
let n = v.len();
let mut cur = vec![];
let mut res = vec![];
Self::dfs(0, &mut cur, &mut res, &v, n);
res
}

fn dfs(start: usize, cur: &mut Vec<char>, all: &mut Vec<String>, v: &[Vec<char>], n: usize) {
if start == n {
all.push(cur.iter().copied().collect());
} else {
for &c in &v[start] {
cur.push(c);
Self::dfs(start + 1, cur, all, v, n);
cur.pop();
}
}
}
}

#[test]
fn test() {
let s = "{a,b}c{d,e}f".to_string();
let res: Vec<String> = vec_string!["acdf", "acef", "bcdf", "bcef"];
assert_eq!(Solution::expand(s), res);
let s = "abcd".to_string();
let res: Vec<String> = vec_string!["abcd"];
assert_eq!(Solution::expand(s), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.