Show problems as
Classic problem #1087MediumStringBacktrackingStackBreadth-First SearchSorting

Brace Expansion

Real-world version: Every Code A Part Template Allows
Tracked in this browser only
Read Brace Expansion on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A catalogue writes a family of part codes as one template s, built from lowercase letters and from groups wrapped in curly brackets. A group such as {a,c,f} lists its options separated by commas; the options inside one group are single letters, all different from each other, and a group is never written inside another group. A letter outside every bracket appears in the code as it stands, and each group supplies exactly one of its letters.

Return every part code the template allows, in lexicographic order, that is the order a dictionary would list them in.

Examples

Example 1

Input
s = "{a,b}p{c,d}"
Output
["apc", "apd", "bpc", "bpd"]

The first group supplies a or b, the letter p is fixed, and the second group supplies c or d. All four codes are listed in dictionary order.

Example 2

Input
s = "{b,a}"
Output
["a", "b"]

The template is one group offering b or a, so the codes are the single letters a and b, listed in dictionary order rather than in the order the template wrote them.

Example 3

Input
s = "{q}"
Output
["q"]

The group offers one option, so the template allows the single code q.

Constraints

  • 1 <= s.length <= 50
  • s consists of curly brackets, commas and lowercase English letters.
  • s is guaranteed to be a valid template.
  • No group appears inside another group.
  • The letters listed inside one group are all different.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def expand(s: str) -> list[str]:
Java
public String[] expand(String s)

More on the same topics