1096. 花括号展开 II
如果你熟悉 Shell 编程，那么一定了解过花括号展开，它可以用来生成任意字符串。
花括号展开的表达式可以看作一个由 花括号、逗号 和 小写英文字母 组成的字符串，定义下面几条语法规则：
如果只给出单一的元素 x，那么表达式表示的字符串就只有 "x"。R(x) = {x}
例如，表达式 "a" 表示字符串 "a"。
而表达式 "w" 就表示字符串 "w"。
当两个或多个表达式并列，以逗号分隔，我们取这些表达式中元素的并集。R({e_1,e_2,...}) = R(e_1) ∪ R(e_2) ∪ ...
例如，表达式 "{a,b,c}" 表示字符串 "a","b","c"。
而表达式 "{{a,b},{b,c}}" 也可以表示字符串 "a","b","c"。
要是两个或多个表达式相接，中间没有隔开时，我们从这些表达式中各取一个元素依次连接形成字符串。R(e_1 + e_2) = {a + b for (a, b) in R(e_1) × R(e_2)}
例如，表达式 "{a,b}{c,d}" 表示字符串 "ac","ad","bc","bd"。
表达式之间允许嵌套，单一元素与表达式的连接也是允许的。
例如，表达式 "a{b,c,d}" 表示字符串 "ab","ac","ad"。
例如，表达式 "a{b,c}{d,e}f{g,h}" 可以表示字符串 "abdfg", "abdfh", "abefg", "abefh", "acdfg", "acdfh", "acefg", "acefh"。
给出表示基于给定语法规则的表达式 expression，返回它所表示的所有字符串组成的有序列表。
假如你希望以「集合」的概念了解此题，也可以通过点击 “显示英文描述” 获取详情。
示例 1：
输入：expression = "{a,b}{c,{d,e}}"
输出：["ac","ad","ae","bc","bd","be"]
示例 2：
输入：expression = "{{a,z},a{b,c},{ab,z}}"
输出：["a","ab","ac","z"]
解释：输出中 不应 出现重复的组合结果。
提示：
1 <= expression.length <= 60
expression[i] 由 '{'，'}'，',' 或小写英文字母组成
给出的表达式 expression 用以表示一组基于题目描述中语法构造的字符串解答：表达式求值
class Solution {
public List<String> merge(List<List<String>> vs) {
// pre 初值为[""], 每次循环都将 pre 更新为上一次循环的结果
List<String> pre = Arrays.asList("");
for (List<String> cur : vs) { // 遍历当前括号内的字符串列表
List<String> tmp = new ArrayList<>(); // 临时存储结果
for (String p : pre) { // 遍历上一次循环得到的结果
for (String s : cur) { // 遍历当前括号内的字符串
tmp.add(p + s); // 将上一次结果和当前字符串拼接，并加入结果列表
}
}
pre = tmp; // 更新结果
}
return pre; // 返回结果
}
public List<String> braceExpansionII(String expression) {
Set<String> set = new TreeSet<>(); // 使用 TreeSet 自动去重和排序
List<List<String>> vs = new ArrayList<>(); // 存储括号内的字符串列表
int lv = 0; // 记录当前括号嵌套深度
int start = 0; // 记录当前括号起始位置
for (int i = 0; i < expression.length(); i++) {
if (expression.charAt(i) == '{') { // 遇到左括号
if (lv++ == 0) { // 如果是最外层括号
start = i + 1; // 记录起始位置
}
} else if (expression.charAt(i) == '}') { // 遇到右括号
if (--lv == 0) { // 如果是最外层括号
vs.add(braceExpansionII(expression.substring(start, i))); // 将括号内的字符串递归处理，并加入列表
}
} else if (expression.charAt(i) == ',' && lv == 0) { // 遇到逗号，表示括号内的字符串已经结束
set.addAll(merge(vs)); // 将括号内的字符串列表合并，并加入结果集合
vs.clear(); // 清空列表
} else if (lv == 0) { // 遇到普通字符，如果不在括号内
vs.add(Arrays.asList(expression.charAt(i) + "")); // 将字符转化为字符串，并加入列表
}
}
set.addAll(merge(vs)); // 处理最后一组括号内的字符串，并加入结果集合
return new ArrayList<>(set); // 将集合转化为列表并返回
}
}
