2023-07-13：如果你熟悉 Shell 编程，那么一定了解过花括号展开，它可以用来生成任意字符串。

花括号展开的表达式可以看作一个由 花括号、逗号 和 小写英文字母 组成的字符串

定义下面几条语法规则：

如果只给出单一的元素 x，那么表达式表示的字符串就只有 “x”。R(x) = {x}

例如，表达式 “a” 表示字符串 “a”。

而表达式 “w” 就表示字符串 “w”。

当两个或多个表达式并列，以逗号分隔，我们取这些表达式中元素的并集

R({e_1,e_2,…}) = R(e_1) ∪ R(e_2) ∪ …

例如，表达式 “{a,b,c}” 表示字符串 “a”,“b”,“c”。

而表达式 “{{a,b},{b,c}}” 也可以表示字符串 “a”,“b”,“c”。

要是两个或多个表达式相接，中间没有隔开时，

我们从这些表达式中各取一个元素依次连接形成字符串

R(e_1 + e_2) = {a + b for (a, b) in R(e_1) × R(e_2)}

例如，表达式 “{a,b}{c,d}” 表示字符串 “ac”,“ad”,“bc”,“bd”。

表达式之间允许嵌套，单一元素与表达式的连接也是允许的。

例如，表达式 “a{b,c,d}” 表示字符串 “ab”,“ac”,"ad"​​​​​​。

例如，表达式 “a{b,c}{d,e}f{g,h}”

可以表示字符串 :

“abdfg”, “abdfh”, “abefg”, “abefh”,

“acdfg”, “acdfh”, “acefg”, “acefh”。

给出表示基于给定语法规则的表达式 expression。

返回它所表示的所有字符串组成的有序列表。

输入：expression = “{a,b}{c,{d,e}}”。

输出：[“ac”,“ad”,“ae”,“bc”,“bd”,“be”]。

答案2023-07-13：

大体步骤如下：

1.定义了一个结构体 Info，其中包含一个 treeset.Set 类型的指针 ans 和一个整数 end。

2.定义了一个 NewInfo 函数，用于初始化 Info 对象。

3.定义了 braceExpansionII 函数，接收一个表示表达式的字符串，并返回展开后的字符串列表。

4.process 函数是实际处理展开过程的核心函数，它接收一个表示表达式的字符数组 exp 和一个起始索引 start，返回一个 Info 对象。

5.在 process 函数中，创建了一个空的 treeset.Set 对象 ans 和一个空的 []*treeset.Set 切片 parts。

6.使用 strings.Builder 创建了一个字符串构建器 builder。

7.在循环中，依次遍历 exp 中的字符，直到遇到 } 或到达字符串末尾为止。

8.如果当前字符为 {，则调用 addStringToParts 函数将构建器中的字符串添加到 parts 中，并递归调用 process 函数处理 {} 内部的表达式，将返回的 ans 添加到 parts 中，并更新起始索引 start。

9.如果当前字符为 ,，则调用 addStringToParts 函数将构建器中的字符串添加到 parts 中，并将 parts 中的所有集合添加到 ans 中，然后清空 parts，并更新起始索引 start。

10.如果当前字符为小写英文字母，则将其添加到构建器中。

11.循环结束后，调用 addStringToParts 函数将构建器中的最后一个字符串添加到 parts 中。

12.调用 addPartsToSet 函数将 parts 中的所有集合添加到 ans 中。

13.返回包含 ans 和起始索引 start 的 Info 对象。

14.addStringToParts 函数将构建器中的字符串添加到 parts 中，如果构建器不为空，则创建一个新的 treeset.Set 对象，并将字符串添加到集合中，再将集合添加到 parts 中。

15.addPartsToSet 函数将 parts 中的所有集合进行组合并添加到 ans 中。

16.processParts 函数是递归处理 parts 切片的核心函数。如果索引 i 等于 parts 的长度，则表示已经处理完所有集合，将连接后的字符串添加到 ans 中。否则，取出当前集合，遍历集合中的每个元素，与 path 进行连接，并递归调用 processParts 处理下一个集合。

17.toSlice 函数将 ans 中的元素转换为有序字符串切片，并返回该切片。

18.在 main 函数中，定义了一个表达式字符串 expression，并调用 braceExpansionII 函数对表达式进行展开，并将结果打印输出。

该代码的时间复杂度为 $O(N^M)$，其中N为表达式中的字符数，M为展开括号的深度。具体来说，代码中的核心函数process通过遍历表达式字符并进行递归处理，每次递归都会将问题规模缩小，直到达到展开括号的最深层级。因此，时间复杂度取决于表达式中字符的数量以及展开括号的深度。

空间复杂度是 $O(N^M)$，其中N为表达式中的字符数，M为展开括号的深度。在代码执行过程中，会创建一些辅助数据结构，如字符串构建器和集合。对于集合这种动态数据结构，其占用的内存空间与展开括号的深度呈指数关系。而字符串构建器的空间复杂度与表达式中字符的数量成线性关系。因此，最终的空间复杂度取决于展开括号的深度和表达式中字符的数量，即 $O(N^M)$。

go完整代码如下：

package main

import (
	"fmt"
	"strings"

	"github.com/emirpasic/gods/sets/treeset"
)

type Info struct {
	ans *treeset.Set
	end int
}

func NewInfo(a *treeset.Set, e int) *Info {
	ans := &Info{}
	ans.ans = a
	ans.end = e
	return ans
}

func braceExpansionII(expression string) []string {
	ans := process([]rune(expression), 0).ans
	return toSlice(ans)
}

func process(exp []rune, start int) *Info {
	ans := treeset.NewWith(func(a, b interface{}) int {
		aa := a.(string)
		bb := b.(string)
		if aa < bb {
			return -1
		} else if aa == bb {
			return 0
		} else {
			return 1
		}
	})
	parts := make([]*treeset.Set, 0)
	builder := strings.Builder{}

	for start < len(exp) && exp[start] != '}' {
		if exp[start] == '{' {
			addStringToParts(&builder, &parts)
			next := process(exp, start+1)
			parts = append(parts, next.ans)
			start = next.end + 1
		} else if exp[start] == ',' {
			addStringToParts(&builder, &parts)
			addPartsToSet(ans, &parts)
			start++
			parts = make([]*treeset.Set, 0)
		} else {
			builder.WriteRune(exp[start])
			start++
		}
	}

	addStringToParts(&builder, &parts)
	addPartsToSet(ans, &parts)
	return &Info{ans, start}
}

func addStringToParts(builder *strings.Builder, parts *[]*treeset.Set) {
	if builder.Len() != 0 {
		s := treeset.NewWithStringComparator()
		s.Add(builder.String())
		*parts = append(*parts, s)
		builder.Reset()
	}
}

func addPartsToSet(ans *treeset.Set, parts *[]*treeset.Set) {
	processParts(parts, 0, "", ans)
}

func processParts(parts *[]*treeset.Set, i int, path string, ans *treeset.Set) {
	if i == len(*parts) {
		if path != "" {
			ans.Add(path)
		}
	} else {
		part := (*parts)[i]
		it := part.Iterator()
		for it.Next() {
			cur := it.Value().(string)
			processParts(parts, i+1, path+cur, ans)
		}
	}
}

func toSlice(set *treeset.Set) []string {
	slice := make([]string, 0)
	it := set.Iterator()
	for it.Next() {
		slice = append(slice, it.Value().(string))
	}
	return slice
}

func main() {
	expression := "{a,b}{c,{d,e}}"
	result := braceExpansionII(expression)
	fmt.Println(result)
}