LeetCode 1096. 花括号展开 II

2022-02-03 HGNULB 约 12 分钟

文章信息 6 个分类 6 个标签

分类

题目描述

✅ 1096. 花括号展开 II

题意分析

给一个由小写字母、逗号、花括号组成的表达式，要求算出它能表示的全部字符串，去重后按字典序返回。表达式里逗号表示「或」（并集），相邻并列表示「拼接」（笛卡尔积），花括号可以任意层嵌套。

关键是把这门小语言的规则读准：并集与拼接的优先级不同，拼接比逗号结合得更紧。{a,b}c 的意思是 ac 和 bc，而不是 a 和 bc；只有花括号能改变这个结合顺序。这直接决定了后面必须写一个分层的处理过程，而不能一遍扫到底。

括号可以嵌套，且嵌套深度不由题目直接给出，说明处理过程必须能「自己调用自己」或者用一个显式的栈来记住外层没处理完的部分——这是所有需要处理任意深度嵌套结构的题目共同的信号。

结果要求去重且有序。{a,a} 只算一个 a，{{a,b},{b,c}} 里的 b 也只算一次，所以中间过程就应该用集合承载，最后再统一排序。

边界：表达式可能根本没有括号（就是一个单词）；也可能是 {a} 这种只含一个选项的括号；空串不会出现，题目保证表达式合法，因此不需要做语法错误处理。

数据规模只有 60 个字符，结果集也不会爆炸，所以不需要在集合合并上做特别的优化，把语义写对才是重点。

解法：递归解析表达式

核心思路

先想暴力：把最内层的一对花括号找出来、展开、替换回原串，再重复。这个做法能出结果，但每次替换都要重建整个字符串，而且展开后又会生成新的可展开位置，代码里到处是下标偏移的修补，写不干净也说不清正确性。瓶颈在于它把「结构」当成「文本」来处理。

换个角度观察：这个表达式其实有一套非常规整的文法，只有三层。

expr = term (',' term)*：若干个 term 用逗号并列，语义是并集。

term = factor+：若干个 factor 直接相邻，语义是笛卡尔积拼接。

factor = 小写字母串 | '{' expr '}'：一个 factor 要么是一个单词，要么是一对花括号包住的完整 expr。

这三条规则互相引用，恰好构成递归下降解析（recursive descent）的三个函数。文法把优先级写死在结构里：term 在 expr 内部被调用，所以拼接天然比逗号绑得紧；factor 里的 { expr } 又让括号内部重新回到最低优先级，嵌套问题自动解决。

每个函数的返回值统一定义为该语法片段能展开出的全部字符串的集合，这是整个解法的不变量。有了它，三个函数各自要做的事就唯一确定了：

parseExpr 把各个 term 的集合求并；

parseTerm 把各个 factor 的集合求笛卡尔积后逐对拼接，初值是 {""}（拼接运算的单位元，保证第一个 factor 能正确并入）；

parseFactor 遇到字母就返回单元素集合，遇到 { 就吃掉左括号、递归调用 parseExpr、再吃掉右括号。

三个函数共享同一个游标 idx，约定是：进入函数时 idx 指向本片段的第一个字符，返回时 idx 指向本片段之后的第一个字符。这个约定必须严格遵守，否则调用方与被调用方对位置的理解就会错位。Java 里用 int[1] 模拟引用传递，Go 里用 *int。

正确性可以按文法结构归纳：factor 对单词直接返回唯一展开，对花括号递归得到括号内全部展开；若每个 factor 都正确，term 的连续笛卡尔积就恰好枚举所有拼接组合；若每个 term 都正确，expr 求并集就恰好覆盖逗号两侧的全部选择。集合消除重复，最外层排序只改变顺序，不改变结果。

最后把集合倒进 List 排序输出。集合天然完成去重，排序只在最外层做一次。

解题步骤

定义游标契约：用一个可被所有递归层共享的下标 idx。之所以不能用普通的 int 参数，是因为子函数消耗了多少字符必须让父函数知道，返回值已经被集合占用了，位置只能靠引用带回来。

parseFactor：识别最小单元。先看当前字符是不是 {。是则 idx++ 跳过左括号，递归 parseExpr 拿到括号内的全部结果，再 idx++ 跳过右括号后返回——两次自增分别对应吃掉一个定界符，缺一个都会让后续解析读到错位的字符。否则一路收集小写字母，直到遇到 {、}、, 三种定界符之一或串尾为止，把这个单词作为唯一元素返回。

parseTerm：处理拼接。结果初始化为 {""} 而不是空集，因为空集与任何集合做笛卡尔积仍是空集，第一个 factor 会被吞掉；{""} 是拼接的单位元，能让循环从第一轮就正常工作。循环条件是「没到串尾，且当前字符既不是 } 也不是 ,」——这两个字符正是 term 的两种合法终止符，读到它们就把控制权交还给上层，不能自作主张消耗掉。每轮取一个 factor 的集合，与已有结果做两重循环拼接。

parseExpr：处理并集。先解析一个 term，然后只要当前字符是 , 就 idx++ 跳过逗号、再解析一个 term 并把结果并入。注意这里是 addAll 求并，不是拼接——这一行就是「逗号优先级最低」的具体体现。

收尾：从下标 0 调用 parseExpr，把返回的集合转成列表排序。排序放在最外层做一次即可，中间层排序纯属浪费。

以 {a,b}{c,{d,e}} 走一遍（记 idx 为当前位置）：

parseExpr(0) 调 parseTerm(0)，结果初值 {""}。第一轮 parseFactor 看到 idx=0 是 {，跳到 1 后递归 parseExpr(1)：它解析出 term a（读到 , 停下），随后吃掉逗号解析出 term b，得到 {a, b}，此时 idx=4 指向 }；回到 parseFactor 吃掉右括号，idx=5，返回 {a, b}。term 层做拼接：{""} × {a,b} = {a, b}。

第二轮 parseFactor 看到 idx=5 是 {，跳到 6 递归 parseExpr(6)：先得 term c（idx=7 指向 ,），吃掉逗号后 parseTerm(8) 的第一个 factor 又是 {，再递归一层解析出 {d, e}，该层 term 结果为 {d, e}，并入后得 {c, d, e}，idx 停在最外层的 }；回到 parseFactor 吃掉它，返回 {c, d, e}。term 层再做拼接：{a,b} × {c,d,e} 得到 {ac, ad, ae, bc, bd, be}。

此时 idx 到达串尾，parseTerm 与 parseExpr 依次退出，排序后返回 ["ac","ad","ae","bc","bd","be"]。

若把 parseTerm 的初值写成空集，第一轮的两重循环一次都不会执行，结果永远是空集；若 parseTerm 的循环条件忘了判 ,，parseFactor 会在逗号处返回空字符串且不移动游标，外层循环永远停在同一位置。

代码实现

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<String> braceExpansionII(String expression) {
        int[] idx = new int[1];
        Set<String> res = parseExpr(expression, idx);
        List<String> list = new ArrayList<>(res);
        Collections.sort(list);
        return list;
    }

    // expr = term (',' term)*，逗号表示并集。
    private Set<String> parseExpr(String s, int[] idx) {
        Set<String> res = parseTerm(s, idx);
        while (idx[0] < s.length() && s.charAt(idx[0]) == ',') {
            idx[0]++;
            res.addAll(parseTerm(s, idx));
        }
        return res;
    }

    // term = factor+，相邻表示笛卡尔积拼接，初值取单位元 {""}。
    private Set<String> parseTerm(String s, int[] idx) {
        Set<String> res = new HashSet<>();
        res.add("");
        while (idx[0] < s.length() && s.charAt(idx[0]) != '}' && s.charAt(idx[0]) != ',') {
            Set<String> next = parseFactor(s, idx);
            Set<String> merged = new HashSet<>();
            for (String a : res) {
                for (String b : next) {
                    merged.add(a + b);
                }
            }
            res = merged;
        }
        return res;
    }

    // factor 可能是单词或 {expr}。
    private Set<String> parseFactor(String s, int[] idx) {
        Set<String> res = new HashSet<>();
        if (s.charAt(idx[0]) == '{') {
            idx[0]++;
            res = parseExpr(s, idx);
            idx[0]++;
            return res;
        }

        StringBuilder sb = new StringBuilder();
        while (idx[0] < s.length()) {
            char c = s.charAt(idx[0]);
            if (c == '{' || c == '}' || c == ',') {
                break;
            }
            sb.append(c);
            idx[0]++;
        }
        res.add(sb.toString());
        return res;
    }
}

import "sort"

func braceExpansionII(expression string) []string {
	idx := 0
	res := parseExpr(expression, &idx)
	list := make([]string, 0, len(res))
	for k := range res {
		list = append(list, k)
	}
	sort.Strings(list)
	return list
}

// expr = term (',' term)*，逗号表示并集。
func parseExpr(s string, idx *int) map[string]struct{} {
	res := parseTerm(s, idx)
	for *idx < len(s) && s[*idx] == ',' {
		*idx = *idx + 1
		term := parseTerm(s, idx)
		for k := range term {
			res[k] = struct{}{}
		}
	}
	return res
}

// term = factor+，相邻表示笛卡尔积拼接，初值取单位元 {""}。
func parseTerm(s string, idx *int) map[string]struct{} {
	res := map[string]struct{}{"": {}}
	for *idx < len(s) && s[*idx] != '}' && s[*idx] != ',' {
		next := parseFactor(s, idx)
		merged := make(map[string]struct{})
		for a := range res {
			for b := range next {
				merged[a+b] = struct{}{}
			}
		}
		res = merged
	}
	return res
}

// factor 可能是单词或 {expr}。
func parseFactor(s string, idx *int) map[string]struct{} {
	res := make(map[string]struct{})
	if s[*idx] == '{' {
		*idx = *idx + 1
		res = parseExpr(s, idx)
		*idx = *idx + 1
		return res
	}

	start := *idx
	for *idx < len(s) {
		c := s[*idx]
		if c == '{' || c == '}' || c == ',' {
			break
		}
		*idx = *idx + 1
	}
	res[s[start:*idx]] = struct{}{}
	return res
}

复杂度分析

时间复杂度：这是输出敏感算法。设 P 为所有笛卡尔积循环累计生成的候选字符串数，L 为候选字符串最大长度（L ≤ n），K 为最终去重后的结果数；字符串拼接与哈希均需按长度计费，因此解析与展开为 $O(n + P L)$，最终排序为 $O(K L \log K)$。最坏情况下 P、K 都可随表达式长度指数增长，而仅输出 K 个答案就已经无法避免这部分代价。

空间复杂度：$O(n + U L)$，其中 U 是递归过程中同时存活的中间字符串与最终字符串数量；O(n) 来自最坏嵌套深度的调用栈。结果集本身可能是指数级，不能写成只依赖表达式长度的多项式空间。

关键点总结

面对带任意深度嵌套的表达式，第一步永远是先写出文法再写代码。文法一旦写清楚，函数划分、优先级、终止条件就全部确定了，这是面试中最该先说出口的一步。

递归下降的每个函数都要有明确的返回语义（这里是「该片段能展开的集合」）和明确的游标契约（进来指向头、出去指向尾后一位），两个约定共同保证各层能拼装正确。

逗号=并集、相邻=笛卡尔积，两种运算的优先级差异靠函数调用层次表达，不靠额外的优先级表。

拼接类归并的初值取单位元 {""}，这是「乘法从 1 开始、加法从 0 开始」在字符串集合上的对应物。

用集合承载中间结果，候选字符串插入时同步去重；字典序只影响最终输出，所以排序只在最外层做一次。

复杂度必须按输出规模分析：笛卡尔积会真实构造每个组合，结果数可能指数增长；这是题目输出决定的下界，不是递归解析带来的额外浪费。

面试视角：这道题与 394 字符串解码、224 基本计算器是同一族。若面试官要求不用递归，可以答「用一个显式栈保存每层未完成的集合，遇到 { 压栈、遇到 } 弹栈合并」，本质与递归等价。

易错点总结

错误写法：parseTerm 的结果初始化为空集合。用例 {a,b}：第一轮两重循环因外层为空直接跳过，最终返回空集合，答案变成 []。

错误写法：parseFactor 处理 { 时只 idx++ 跳过左括号，忘了返回前再 idx++ 跳过右括号。用例 {a}b：返回后游标仍停在 } 上，parseTerm 的循环条件立刻判定终止，b 被永久丢弃，答案是 ["a"]。

错误写法：parseTerm 的循环条件只写 idx < n && s[idx] != '}'，漏了 != ','。用例 {a,b}：游标停在逗号时，parseFactor 立即返回空字符串且没有推进游标，parseTerm 因而陷入死循环。

错误写法：parseExpr 里把 res.addAll(parseTerm(...)) 写成拼接（两重循环相加）。用例 {a,b}：得到的是 ["ab"] 而不是 ["a","b"]，并集被误当成了乘积。

错误写法：把 idx 声明成普通 int 形参逐层传值。用例 {a,b}c：子调用消耗的字符数传不回父层，父层仍从 { 之后一位继续读，游标彻底错乱，输出无意义。

错误写法：parseFactor 读单词时只在遇到 { 时停止，没把 } 和 , 也作为终止符。用例 {ab,c}：单词会一路读到 ,，把定界符吃进字符串里。

错误写法：用 List 代替 Set 存中间结果。用例 {a,a}b：ab 会出现两次，最终答案含重复项，题目明确要求去重。

错误写法：在每一层 parseExpr 返回前都排序。功能上不错但白白多做 $O(k \log k)$ 的工作，嵌套深时开销叠加，面试官会追问为什么。

错误写法：直接对 HashSet 的迭代顺序抱有期望，不做最终排序。用例 {b,a}：哈希顺序可能输出 ["b","a"]，不满足字典序要求。

相似题目

题目	难度	考察点
1087. 花括号展开	中等	本题的简化版，括号不嵌套且只在顶层并列，一次遍历分组后回溯即可
394. 字符串解码	中等	括号带重复次数前缀，栈里要同时压数字与已拼前缀，语义是重复不是并集
224. 基本计算器	困难	同为递归下降，但要处理带符号数与括号取负，返回值是数值而非集合
726. 原子的数量	困难	括号后带倍数，返回值是「元素到个数」的映射，合并时做计数相加
736. Lisp 语法解析	困难	文法更复杂且带变量作用域，递归时要额外携带一层符号表
385. 迷你语法分析器	中等	解析嵌套列表结构，练习同样的游标契约，但输出是树形对象