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

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

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

如果只給出單一的元素 x，那么表達(dá)式表示的字符串就只有 "x"。R(x) = {x}

例如，表達(dá)式 "a" 表示字符串 "a"。

而表達(dá)式 "w" 就表示字符串 "w"。

當(dāng)兩個(gè)或多個(gè)表達(dá)式并列，以逗號分隔，我們?nèi)∵@些表達(dá)式中元素的并集

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

例如，表達(dá)式 "{a,b,c}" 表示字符串 "a","b","c"。

而表達(dá)式 "{{a,b},{b,c}}" 也可以表示字符串 "a","b","c"。

要是兩個(gè)或多個(gè)表達(dá)式相接，中間沒有隔開時(shí)，

我們從這些表達(dá)式中各取一個(gè)元素依次連接形成字符串

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

例如，表達(dá)式 "{a,b}{c,d}" 表示字符串 "ac","ad","bc","bd"。

表達(dá)式之間允許嵌套，單一元素與表達(dá)式的連接也是允許的。

例如，表達(dá)式 "a{b,c,d}" 表示字符串 "ab","ac","ad"。

例如，表達(dá)式 "a{b,c}{d,e}f{g,h}"

可以表示字符串 :

"abdfg", "abdfh", "abefg", "abefh",

"acdfg", "acdfh", "acefg", "acefh"。

給出表示基于給定語法規(guī)則的表達(dá)式 expression。

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

輸入：expression = "{a,b}{c,{d,e}}"。

輸出：["ac","ad","ae","bc","bd","be"]。

答案2023-07-13：

大體步驟如下：

1.定義了一個(gè)結(jié)構(gòu)體?Info，其中包含一個(gè)?treeset.Set?類型的指針?ans?和一個(gè)整數(shù)?end。

2.定義了一個(gè)?NewInfo?函數(shù)，用于初始化?Info?對象。

3.定義了?braceExpansionII?函數(shù)，接收一個(gè)表示表達(dá)式的字符串，并返回展開后的字符串列表。

4.process?函數(shù)是實(shí)際處理展開過程的核心函數(shù)，它接收一個(gè)表示表達(dá)式的字符數(shù)組?exp?和一個(gè)起始索引?start，返回一個(gè)?Info?對象。

5.在?process?函數(shù)中，創(chuàng)建了一個(gè)空的?treeset.Set?對象?ans?和一個(gè)空的?[]*treeset.Set?切片?parts。

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

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

8.如果當(dāng)前字符為?{，則調(diào)用?addStringToParts?函數(shù)將構(gòu)建器中的字符串添加到?parts?中，并遞歸調(diào)用?process?函數(shù)處理?{}?內(nèi)部的表達(dá)式，將返回的?ans?添加到?parts?中，并更新起始索引?start。

9.如果當(dāng)前字符為?,，則調(diào)用?addStringToParts?函數(shù)將構(gòu)建器中的字符串添加到?parts?中，并將?parts?中的所有集合添加到?ans?中，然后清空?parts，并更新起始索引?start。

10.如果當(dāng)前字符為小寫英文字母，則將其添加到構(gòu)建器中。

11.循環(huán)結(jié)束后，調(diào)用?addStringToParts?函數(shù)將構(gòu)建器中的最后一個(gè)字符串添加到?parts?中。

12.調(diào)用?addPartsToSet?函數(shù)將?parts?中的所有集合添加到?ans?中。

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

14.addStringToParts?函數(shù)將構(gòu)建器中的字符串添加到?parts?中，如果構(gòu)建器不為空，則創(chuàng)建一個(gè)新的?treeset.Set?對象，并將字符串添加到集合中，再將集合添加到?parts?中。

15.addPartsToSet?函數(shù)將?parts?中的所有集合進(jìn)行組合并添加到?ans?中。

16.processParts?函數(shù)是遞歸處理?parts?切片的核心函數(shù)。如果索引?i?等于?parts?的長度，則表示已經(jīng)處理完所有集合，將連接后的字符串添加到?ans?中。否則，取出當(dāng)前集合，遍歷集合中的每個(gè)元素，與?path?進(jìn)行連接，并遞歸調(diào)用?processParts?處理下一個(gè)集合。

17.toSlice?函數(shù)將?ans?中的元素轉(zhuǎn)換為有序字符串切片，并返回該切片。

18.在?main?函數(shù)中，定義了一個(gè)表達(dá)式字符串?expression，并調(diào)用?braceExpansionII?函數(shù)對表達(dá)式進(jìn)行展開，并將結(jié)果打印輸出。

該代碼的時(shí)間復(fù)雜度為$O(N^M)$，其中N為表達(dá)式中的字符數(shù)，M為展開括號的深度。具體來說，代碼中的核心函數(shù)process通過遍歷表達(dá)式字符并進(jìn)行遞歸處理，每次遞歸都會將問題規(guī)模縮小，直到達(dá)到展開括號的最深層級。因此，時(shí)間復(fù)雜度取決于表達(dá)式中字符的數(shù)量以及展開括號的深度。

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