1096. Brace Expansion II

题目信息

题号:

1096

难度:

Hard

主题:

表达式解析、集合并集、字符串连接

原题:

LeetCode 1096

重点:

逗号表示结果集合的并集,相邻表达式表示笛卡尔连接,花括号可以嵌套;最终结果去重并按字典序返回

题目重述

给定由小写字母、花括号和逗号组成的合法表达式 expression。单个字母表示只含该字符串的集合;逗号分隔的表达式表示集合并集;两个表达式直接相邻表示把左侧每个字符串与右侧每个字符串连接。花括号用于分组,并且可以嵌套。

求出表达式能够生成的所有不同字符串,删除重复结果后按字典序升序返回。连接运算与并集运算需要遵循表达式的分组结构。

1 <= expression.length <= 60,表达式合法且只包含小写英文字母、{、} 和 ,。

自建示例

并集结果继续与后续字符连接:

输入:expression = "{a,b}c"
输出:["ac","bc"]
解释:花括号产生 a 和 b 两种选择,每个结果再与字符 c 连接,最后按字典序返回。

表达式只有一个字母:

输入:expression = "x"
输出:["x"]
解释:单个字母表示只包含该字符串的单元素集合。