前言

遞歸調(diào)用，代碼非常的簡潔。但是可以通過顯式棧來模擬棧中的內(nèi)容，鍛煉自己的代碼能力，清楚知道棧幀中需要的內(nèi)容。

一、花括號展開II

二、棧模擬dfs

每碰到一個左括號，就壓一次棧，但棧里面存什么？
存set，由于存在組合，組合之前還不能提前求并集，所以存set切片！！
每碰到一個右括號，就把當(dāng)前set切片整理成一個set，拋向上一層的set切片末尾，根據(jù)前面的操作符，再判定是否需要組合。

func braceExpansionII(expression string) []string {// 模擬函數(shù)調(diào)用棧，數(shù)據(jù)棧和操作符棧。stack := make([][]map[string]interface{},1)top := 1lastOp := make([]byte,0) // 0代表需要組合，1代表不用組合。t := 0lastCh := ',' // 初始化，表示不用組合，set取交集即可。for _,e := range expression {// 碰到括號就壓棧if e == '{' {stack = append(stack[:top],make([]map[string]interface{},0))top++// 當(dāng)前面字符是'}' 或者 字符時，需要組合，將組合操作符壓棧。if lastCh != '{' && lastCh != ','{lastOp = append(lastOp[:t],0)t++}// 如果前面是'{'，說明是該層第一個set塊，當(dāng)該set塊提交上來時不用做任何操作。if lastCh == '{' {lastOp = append(lastOp[:t],1)t++}lastCh = econtinue}// 碰到右括號，先把元素合并向上拋，再根據(jù)操作符來判定是否需要組合。if e == '}' {// 先把元素取交集向上層拋newMap := map[string]interface{}{}curSlice := stack[top - 1]top--for _,sc := range curSlice {for k := range sc {newMap[k] = struct{}{}}}stack[top - 1] = append(stack[top - 1],newMap)// 再根據(jù)操作符進(jìn)行普通放置，還是組合if t != 0 && lastOp[t - 1] == 0 {cur := stack[top - 1]m1,m2 := cur[len(cur) - 1],cur[len(cur) - 2]nm := map[string]interface{}{}for k2 := range m2 {for k1 := range m1 {nm[k2+k1] = struct{}{}}}stack[top - 1] = append(stack[top-1][:len(cur)-2],nm)}// 操作符出棧if t != 0 {t--}}else if e == ',' {lastOp = append(lastOp[:t],1)t++}else {// 右貼字符型，需要立即組合cur := stack[top - 1]if lastCh != ',' && lastCh != '{'{m := cur[len(cur) - 1]nm := map[string]interface{}{}for k := range m {nm[k + string(e)] = struct{}{}}stack[top-1]=append(stack[top-1][:len(cur)-1],nm)}else {m := map[string]interface{}{}m[string(e)] = struct{}{}stack[top - 1] = append(stack[top - 1],m)// 逗號操作符出棧if lastCh == ',' && t != 0 {t--}}}lastCh = e}// 取數(shù)據(jù)并排序return getData(stack[0])// 總：append的使用append+slice[:top]，以及append在修改該當(dāng)前slice的情況
}
func getData(ms []map[string]interface{}) []string{ans := []string{}for _,m := range ms {for k := range m {ans = append(ans,k)}}sort.Slice(ans,func(i,j int)bool{return ans[i] < ans[j]})return ans
}
// ‘,’表示和后面并集（合并去重）；‘空’表示相互組合。
// 根據(jù)花括號配對，以及進(jìn)入下一個括號前碰到的指示操作符，來進(jìn)行組合或并集
// set來做容器，
// 每次向上提交一層，就要看操作符，逗號合井號不管，只管空格符進(jìn)行組合。 這就是整體的抽象規(guī)則。
// 思路：每碰到左括號就壓一層棧，棧幀中存一個個set形成的切片，同時需要用另一個棧存操作符，可能需要組合。
// 當(dāng)碰到組合的情況，當(dāng)前set需要和切片中前一個set進(jìn)行組合。

總結(jié)

1）采用棧模擬遞歸調(diào)用，鍛煉代碼能力，清楚知道棧幀中需要什么內(nèi)容。

參考資料

[1] LeetCode 花括號展開II