Brace Expansion II — LeetCode 1096 Python Solution

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

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

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