#1096
Brace Expansion II
expert · 1145 · lc hard +32 · verified · 63.9% accepted · 506 likes · top 67%
Description
A grammar generates sets of lowercase strings:
- A single letter x represents the set {x}.
- A comma-separated list inside braces represents the union of the sets of each element.
- Concatenating two expressions produces all pairs of concatenated strings from each set.
Formally, R(x) = {x}; R({e1,e2,...}) = R(e1) ∪ R(e2) ∪ ...; R(e1+e2) = {a+b | a ∈ R(e1), b ∈ R(e2)}.
Given a string expression following this grammar, return the sorted list of distinct words it represents.
Example 1:
Input: expression = "{a,b}{c,{d,e}}"
Output: ["ac","ad","ae","bc","bd","be"]
Example 2:
Input: expression = "{{a,z},a{b,c},{ab,z}}"
Output: ["a","ab","ac","z"]
Explanation: Each distinct word is written only once in the final answer.
Code
1
2
3