Brace Expansion Ii - Leetcode Solution

Problem Statement: Given a string representing a list of words, you need to implement a brace expansion function. A brace expansion consists of a sequence of characters enclosed in curly brackets "{}". We can concatenate one of more sequences to generate a new word. Order of the sequences in the expansion does not matter and duplicates are not allowed.

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

Solution: To solve this problem, we can use a stack and iterate through the characters of the string. When we find an opening brace "{", we push the current stack state onto the stack and clear the current state.

When we find a closing brace "}", we compute the cartesian product of the current stack state and the characters within the braces. We then pop the previous stack state from the stack, and concatenate the current state to the previous state.

Finally, when we reach the end of the string, we return the current stack state.

In order to compute the cartesian product, we can use itertools.product from the Python standard library.

Here's the Python code solution to the problem:

import itertools

def braceExpansionII(expression: str) -> List[str]: stack = [set()] i, n = 0, len(expression)

while i < n:
    c = expression[i]

    if c == "{":
        # New level of braces, push the current state onto the stack
        stack.append(set())
        i += 1
    elif c == "}":
        # Compute the cartesian product of the current state and the characters within the braces
        current = stack.pop()
        prev = stack[-1]
        for prod in itertools.product(prev, current):
            stack[-1].add("".join(prod))
        i += 1
    elif c == ",":
        # Comma separates the characters within a level of braces
        i += 1
    else:
        # Add the character to the current state
        j = i
        while j < n and expression[j].isalpha():
            j += 1
        current = set(expression[i:j])
        prev = stack[-1]
        stack[-1] = set(word + char for word in prev for char in current)
        i = j

return sorted(list(stack[-1]))

The time complexity of the solution is O(2^N * K^M), where N is the number of levels of braces, K is the average length of each set of characters within braces, and M is the maximum length of the input string. The space complexity is O(2^N * K^M).

1