Brace Expansion - Leetcode Solution

Problem Statement:

You are given a string expression representing a list of numbers and/or ranges separated by commas. The expression can also have whitespace characters.

A range is either a single number or a pair of numbers separated by a hyphen (e.g. "0-3" represents the numbers "0,1,2,3").

Return all the numbers in the list in increasing order.

Example 1:

Input: expression = "{a,b}c{d,e}f" Output: ["acdf","acef","bcdf","bcef"] Example 2:

Input: expression = "abcd" Output: ["abcd"] Constraints:

1 <= expression.length <= 50 expression consists of lowercase English letters, digits, and the characters '{', '}', ',' and '-'. expression does not contain any nested curly brackets. All the numbers in the expression are in the range [0, 99].

Solution:

The problem can be solved using recursive approach.

We start by scanning the given expression until we encounter an opening braces "{". After encountering the opening braces, we keep on scanning until we encounter the closing braces "}". Within the braces, we can either have a comma or a hyphen (for range). We recursively solve the subexpression enclosed within the braces.

For example,

We are given the expression {a,b}c{d,e}f

We begin by scanning the first character "{

The next characters we encounter are a,b

We recursively solve "a", "b"

We come back to curly braces and next characters we encounter are d,e

We recursively solve "d", "e"

Now we have all the possible combinations, i.e., acdf, acef, bcdf, bcef

We sort them and return the sorted list as the answer

Code:

The following python code solves the given problem.

class Solution: def expand(self, expression: str) -> List[str]:

    def dfs(output, string, temp):
        if not string:
            output.append(temp)
        else:
            if string[0] == "{":
                i = string.find("}")
                for letter in string[1:i].split(","):
                    dfs(output, string[i+1:], temp+letter)
            else:
                dfs(output, string[1:], temp+string[0])
    
    output = []
    dfs(output, expression, "")
    return sorted(output)

1