这道题灵感来源于 Bash Shell 的 brace expansion 功能。它不仅出现在 Stripe 面试中，也是 Google 等大厂的高频算法题。它考察的是**递归（Recursion）与字符串解析（Parsing）**能力。
题目描述
实现一个函数，将包含花括号 {} 的字符串展开为所有可能的组合列表。
规则
- 逗号分隔：花括号内的内容由逗号分隔，表示可选的项。
{a,b,c}->["a", "b", "c"]
- 前后缀：花括号外的部分会作为前缀或后缀附加到每个选项上。
pre{a,b}post->["preapost", "prebpost"]
- 嵌套与并列：支持多个花括号并列，或者嵌套（部分题目变种支持嵌套）。
{a,b}{1,2}->["a1", "a2", "b1", "b2"](笛卡尔积)
示例
Input: "{a,b}c{d,e}f"
Output: ["acdf", "acef", "bcdf", "bcef"]
oavoservice 解题思路分析
这道题可以看作是一个**深度优先搜索（DFS）或回溯（Backtracking）**问题。
1. 递归策略
我们需要找到字符串中第一个完整的 {...} 结构。
pre: 花括号前的部分。options: 花括号内解析出的列表。post: 花括号后的部分。
对于 options 中的每一个 opt，我们生成一个新的字符串 pre + opt + post。
然后对这个新字符串继续递归调用展开函数，直到字符串中不再包含 {}。
2. 处理并列括号
例如 {a,b}{1,2}。
- 第一次展开：
a{1,2},b{1,2} - 第二次展开：
a1, a2,b1, b2
3. 栈（Stack）方法（非递归）
也可以使用栈来模拟。
- 扫描字符串，遇到
{进栈。 - 遇到
}出栈，处理当前的选项列表，并与栈顶元素进行笛卡尔积合并。
代码片段 (DFS Python)
def expand(s):
if '{' not in s:
return [s]
# 找到第一个右括号 '}'
r = s.find('}')
# 找到该右括号对应的左括号 '{'
l = s.rfind('{', 0, r)
# 提取各部分
prefix = s[:l]
suffix = s[r+1:]
options = s[l+1:r].split(',')
res = []
for opt in options:
# 拼接并递归
# 注意：这里我们消除了最内层的一对括号，继续递归处理剩余部分
res.extend(expand(prefix + opt + suffix))
# 去重并排序（题目通常要求）
return sorted(list(set(res)))
注意： 上述简单 DFS 适用于嵌套不深的情况。如果括号嵌套非常复杂，或者需要严格的从左到右解析，可能需要更复杂的 Parser 逻辑。
算法题总是写不对边界条件？
oavoservice 提供 HackerRank / CodeSignal 满分代写与辅助服务，同时也提供一对一的代码指导。我们会教你如何快速识别题目模式（Pattern Recognition），用模板化的思维秒杀此类字符串处理题。