# Leetcode: Brace Expansion

Brace Expansion

Similar Problems:

A string S represents a list of words.

Each letter in the word has 1 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, “{a,b,c}d{e,f}” represents the list [“ade”, “adf”, “bde”, “bdf”, “cde”, “cdf”].

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

Example 1:

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

Example 2:

```Input: "abcd"
Output: ["abcd"]
```

Note:

1. 1 <= S.length <= 50
2. There are no nested curly brackets.
3. All characters inside a pair of consecutive opening and ending curly brackets are different.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:
```// Blog link: https://code.dennyzhang.com/brace-expansion
// Basic Ideas: backtracking
//
// Complexity:
import ("sort"
"strings")
func backtrack(combination string, l [][]string, pos int, res *[]string) {
if pos == len(l) {
*res = append(*res, combination)
return
}
for _, ch := range l[pos] {
backtrack(combination+string(ch), l, pos+1, res)
}
}
func expand(S string) []string {
l := [][]string{}
entry := ""
for _, ch := range S+"{" {
if ch == '{' || ch == '}' {
if len(entry) != 0 {
items := strings.Split(entry, ",")
sort.Slice(items, func(i, j int) bool {
return items[i] < items[j]
})
l = append(l, items)
}
entry = ""
} else {
entry = entry+string(ch)
}
}

res := []string{}
backtrack("", l, 0, &res)
return res
}
```

Share It, If You Like It.