花括号展开 II【LC1096】
如果你熟悉 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也做不出来，好难啊，想不出来
- 思路：
- 明确以下几点
- 表达式中有两种运算方式：并集相当于加、相接相当于乘
- 逗号代表子表达式中可以选择的选项，相当于并集
- 如果当前字符是’{‘或者字母并且前一个字符为’}'时，为相接需要采用成操作
- 我们应该优先求取相接的结果，然后最后求取并集，将每个结果放入结果集中。
- 可以使用递归的方式处理表达式，按照顺序处理花括号，枚举花括号中的可选项，拼接新的表达式，进行dfs搜索，最后如果没有花括号了，那么可以直接将结果放入。最后将结果按照字典顺序排序
- 递归函数
- 返回值以及参数
- exp（字符串表达式）
- 全局变量：TreeSet<String>(存放符合条件结果的集合，按字典顺序排序)
- 终止条件
当表达式中没有右花括号时，直接将结果加入返回
- 遍历过程
先找到第一个右花括号的位置j，然后从j向左搜索第一个第一个左花括号i，那么可以将字符串分为a=exp[:,i],b=exp[i+1,j],c=exp[j,n−1]，花括号里面的部分b可以按照逗号分为多个字符串bi，对于每个bi，我们将其拼接成新的表达式a+bi+c，然后递归处理新的表达式
class Solution { private TreeSet<String> s = new TreeSet<>(); public List<String> braceExpansionII(String expression) { dfs(expression); return new ArrayList<>(s); } private void dfs(String exp) { int j = exp.indexOf('}'); if (j == -1) { s.add(exp); return; } int i = j; while (exp.charAt(i) != '{') { --i; } String a = exp.substring(0, i); String c = exp.substring(j + 1); for (String b : exp.substring(i + 1, j).split(",")) { dfs(a + b + c); } } } 作者：ylb 链接：https://leetcode.cn/problems/brace-expansion-ii/solutions/2152366/python3javacgotypescript-yi-ti-yi-jie-di-gs64/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
- 时间复杂度：O(n∗2n/4)
- 空间复杂度：O(1)
