---
title: "1087. Brace Expansion"
url: "https://laigary.com/interview/coding/1087-brace-expansion"
type: "note"
section: "coding"
date: "2023-01-27"
updated: "2026-08-03"
tags: ["Backtrack"]
---

# 1087. Brace Expansion

[1087. Brace Expansion](https://leetcode.com/problems/brace-expansion/)

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

## 思路

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

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

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

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

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

### 剩下的就是模板

後面的方法就很簡單了。

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

### 排序不能省

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

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

## 解題方向

```python
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$ 是**乘積**不是加總，所以是指數等級的 —— 但這是輸出本身的大小，逃不掉。