We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Brace Expansion II

Number: 1188

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given a string expression that encodes a set of words using a specific grammar involving letters, commas, and braces, return the sorted list of distinct words that the expression represents. A single letter represents a singleton set. A comma-delimited list inside braces indicates union, and concatenation (implicit when two expressions are juxtaposed) represents the Cartesian product of words from the two sets.

Key Insights

  • Use a recursive descent parser or stack-based approach to evaluate the expression.
  • There are two distinct operations: union (triggered by commas) and concatenation (implied by adjacent expressions).
  • Parentheses (braces) dictate recursion boundaries.
  • Use sets to automatically prevent duplicates.
  • After computing the resultant set, sort it to meet the output requirements.

Space and Time Complexity

Time Complexity: O(2^n) in the worst-case scenario due to the exponential growth in combinations from concatenation, but practical limits are imposed by the small maximum length (<= 60). Space Complexity: O(2^n) in worst-case for storing all intermediate strings, though practical input sizes keep it manageable.

Solution

We can solve this problem using a recursive parsing approach. The main idea is to process the expression character by character while maintaining the current result as a set of words. When we see a letter, we treat it as a set containing that letter. When we encounter a '{', we recursively evaluate the content until the matching '}'. Commas indicate union: we collect disjoint option sets and combine them using set union. Additionally, when two valid parts are adjacent, we perform concatenation by computing the Cartesian product of the current result and the new set. A stack can be used implicitly through recursion to handle nested braces. Once the recursion completes, the final set is converted to a sorted list.

Code Solutions

# Python solution for Brace Expansion II

def braceExpansionII(expression: str):
    # Recursive helper function to evaluate the expression.
    # Returns a tuple (currSet, index) where currSet is the set computed up to the current index.
    def helper(index):
        curr = set()  # Current set for union groups
        curr.add("")  # Identity for concatenation (empty string)
        res = set()   # Result collection for union of parts
        
        while index < len(expression) and expression[index] != '}':
            if expression[index] == '{':
                # Recursively parse the brace-enclosed expression.
                temp_set, index = helper(index + 1)
            elif expression[index].isalpha():
                # Parse the letter as a singleton set
                temp_set = {expression[index]}
                index += 1
            elif expression[index] == ',':
                # Upon comma, union the current result with the ongoing collection, then reset curr.
                res |= curr
                curr = set()
                curr.add("")
                index += 1
                continue
            
            # Concatenation: for each string in the current result 'curr', concatenate with each string in temp_set.
            new_curr = set()
            for pre in curr:
                for suf in temp_set:
                    new_curr.add(pre + suf)
            curr = new_curr
        # Final union with the last collected group if any.
        res |= curr
        return res, index + 1  # Skip the closing brace
        
    # Call helper starting from index 0.
    result, _ = helper(0)
    # Return the sorted list of words.
    return sorted(result)


# Example test
if __name__ == "__main__":
    expression1 = "{a,b}{c,{d,e}}"
    print(braceExpansionII(expression1))  # Expected: ["ac", "ad", "ae", "bc", "bd", "be"]
← Back to All Questions