Every Spelling of a Pattern

Medium

A pattern pattern describes a set of words. Each position of a word is written either as a single character, which then always appears there, or as a comma-separated list of options in curly braces: for example, {a,e,o} means that position may hold a, e or o. So the pattern "s{a,i}t" stands for the words "sat" and "sit". Return every word the pattern describes, in lexicographic order.

Example 1

pattern="{c,b}a{t,r}" → ['bar', 'bat', 'car', 'cat']

The first letter is c or b, the second is always a, the third is t or r. That gives 4 words, listed in alphabetical order.

Example 2

pattern="room{1,2}" → ['room1', 'room2']

Only the last character has options.

Example 3

pattern="tea" → ['tea']

There are no braces, so there is only one word.

Constraints

1 ≤ len(pattern) ≤ 50
Word characters are lowercase English letters and digits
Each pair of braces holds one or more distinct characters separated by commas
Braces are never nested, and commas appear only inside braces

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Breadth-First Search String Backtracking

Similar problems

Expanding Curly Braces Hard Keypad Words Medium All Balanced Bracket Strings Medium Word Traced on a Letter Grid Medium IP Addresses From a Digit String Medium

Input

pattern="{c,b}a{t,r}"

Expected

['bar', 'bat', 'car', 'cat']

Run checks the first 3 tests in your browser. Submit checks all 75 tests on the server, hidden ones included.