2023-07-13：如果你熟悉 Shell 編程，那么一定了解過花括號展開，它可以用來生成任意字符串。

花括號展開的表達式可以看作一個由 花括號、逗號 和 小寫英文字母 組成的字符串

定義下面幾條語法規(guī)則：

如果只給出單一的元素 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"。

給出表示基于給定語法規(guī)則的表達式 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?函數中，創(chuàng)建了一個空的?treeset.Set?對象?ans?和一個空的?[]*treeset.Set?切片?parts。

6.使用?strings.Builder?創(chuàng)建了一個字符串構建器?builder。

7.在循環(huán)中，依次遍歷?exp?中的字符，直到遇到?}?或到達字符串末尾為止。

8.如果當前字符為?{，則調用?addStringToParts?函數將構建器中的字符串添加到?parts?中，并遞歸調用?process?函數處理?{}?內部的表達式，將返回的?ans?添加到?parts?中，并更新起始索引?start。

9.如果當前字符為?,，則調用?addStringToParts?函數將構建器中的字符串添加到?parts?中，并將?parts?中的所有集合添加到?ans?中，然后清空?parts，并更新起始索引?start。

10.如果當前字符為小寫英文字母，則將其添加到構建器中。

11.循環(huán)結束后，調用?addStringToParts?函數將構建器中的最后一個字符串添加到?parts?中。

12.調用?addPartsToSet?函數將?parts?中的所有集合添加到?ans?中。

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

14.addStringToParts?函數將構建器中的字符串添加到?parts?中，如果構建器不為空，則創(chuàng)建一個新的?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通過遍歷表達式字符并進行遞歸處理，每次遞歸都會將問題規(guī)?？s小，直到達到展開括號的最深層級。因此，時間復雜度取決于表達式中字符的數量以及展開括號的深度。

空間復雜度是$O(N^M)$，其中N為表達式中的字符數，M為展開括號的深度。在代碼執(zhí)行過程中，會創(chuàng)建一些輔助數據結構，如字符串構建器和集合。對于集合這種動態(tài)數據結構，其占用的內存空間與展開括號的深度呈指數關系。而字符串構建器的空間復雜度與表達式中字符的數量成線性關系。因此，最終的空間復雜度取決于展開括號的深度和表達式中字符的數量，即$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)
}