HardNo. 1096

Brace Expansion II — LeetCode 1096 Python Solution

Topics
Stack, Breadth-First Search, Hash Table, String, Backtracking, Sorting
Reading time
3 min

The problem

Under the grammar given below, strings can represent a set of lowercase words. Let R(expr) denote the set of words the expression represents.

Example

Input
expression = "{a,b}{c,{d,e}}"
Output
["ac","ad","ae","bc","bd","be"]

Python solution

PythonSolution
class Solution:
    def braceExpansionII(self, expression: str) -> List[str]:
        def dfs(exp):
            j = exp.find('}')
            if j == -1:
                s.add(exp)
                return
            i = exp.rfind('{', 0, j - 1)
            a, c = exp[:i], exp[j + 1 :]
            for b in exp[i + 1 : j].split(','):
                dfs(a + b + c)

        s = set()
        dfs(expression)
        return sorted(s)

Complexity

Time
O(n)
Space · auxiliary
O(n)

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 1096. Brace Expansion II is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0126Word Ladder IIHard
0721Accounts MergeMedium
1202Smallest String With SwapsMedium
0017Letter Combinations of a Phone NumberMedium
0049Group AnagramsMedium
0127Word LadderHard

Frequently asked questions

How hard is LeetCode 1096. Brace Expansion II?

LeetCode 1096. Brace Expansion II is rated Hard on LeetCode.

What is the time complexity of LeetCode 1096. Brace Expansion II?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 1096. Brace Expansion II?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 1096. Brace Expansion II cover?

LeetCode 1096. Brace Expansion II is tagged Stack, Breadth-First Search, Hash Table, String, Backtracking and Sorting on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.