1087. Brace Expansion

──────────────────────────────────────────────────────────────────────

給一個像 "{a,b}c{d,e}f" 的字串：大括號裡的候選挑一個、括號外的字元照抄，回傳所有能組出來的字串，照字典序。

思路

這個題目比較特別一點，一般來說 backtracking 的題目需要窮舉的項目都很明確，這題比較特別的是需要多花一點時間去解析這個字串，光解析字串或許就可以當作一題了。

解析：把整個字串攤成「一排候選清單」

我解析的方法很簡單，就是遇到括號後解析有哪些候選人，如果只是單純的字元，就直接放入陣列。

"{a,b}c{d,e}f"  ->  [['a','b'], ['c'], ['d','e'], ['f']]

關鍵在單純的字元也包成只有一個候選的陣列。這樣一來，括號和非括號就沒有差別了，後面的程式碼不必再區分兩種情況。

剩下的就是模板

後面的方法就很簡單了。

攤平之後，題目變成「每一組挑一個，列出所有組合」—— 就是 Backtracking 模板裡「候選集合怎麼縮」最單純的那一型：候選集合根本不用縮，第 i 層就是 candidates[i]，做完選擇往下一層走就好。收答案的時機是走完所有組（len(curr) == n）。

排序不能省

題目沒有保證大括號裡的候選本身是排好的（只保證同一組裡的字元互不相同），所以 "{b,a}" 是合法輸入，答案必須是 ["a", "b"]。

範例 "{a,b}c{d,e}f" 剛好每組都已經照字典序，很容易讓人以為不用排。

解題方向

class Solution:
    def expand(self, s: str) -> List[str]:
        
        candidates = []

        i = 0

        while i < len(s):
            if s[i] == '{':
                j = i
                while j < len(s):
                    if s[j] == '}':
                        break
                    j += 1
                candidates.append(s[i+1:j].split(','))
                i = j
            else:
                candidates.append([s[i]])
            i += 1

        res = []
        n = len(candidates)
        def backtrack(curr, i):
            if len(curr) == n:
                res.append(''.join(curr))
                return

            candidate = candidates[i]
            for ch in candidate:
                curr.append(ch)
                backtrack(curr, i + 1)
                curr.pop()

        backtrack([], 0)
        res.sort()
        return res

補充

為什麼 backtrack 的順序不是字典序

因為字典序是由候選的順序決定的，而不是由遞迴的形狀決定的。

這個 backtrack 是「由左到右、每層照候選出現的順序」跑，所以產生出來的順序完全複製了候選清單的順序 —— 候選是 ['b','a']，出來就是先 b 後 a。

反過來說，只要在解析時就把每組候選排好（sorted(s[i+1:j].split(','))），輸出天生就是字典序，最後那個 res.sort() 就可以省掉。兩種做法都對，差別只在把排序放在「進去之前」還是「出來之後」。

複雜度

設 $n$ 是輸入字串長度、 $g$ 是組數、 $m$ 是展開後的字串數（等於各組候選數的乘積）、 $L$ 是每個結果的長度。

時間 $O (n + m \times L \times \log m)$ — 解析掃過字串一次是 $O (n)$ ；產生 $m$ 個結果、每個要 $O (L)$ 接起來；最後排序是 $O (m \log m)$ 次比較、每次比較字串又是 $O (L)$
空間 $O (m \times L)$ — 答案本身。另外遞迴深度是 $O (g)$ ，curr 也只有 $O (g)$

$m$ 是乘積不是加總，所以是指數等級的 —— 但這是輸出本身的大小，逃不掉。