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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Brace Expansion

Number: 1076

Difficulty: Medium

Paid? Yes

Companies: DoorDash, Niantic, Google

Problem Description

Given a string s that represents a list of words where each letter in the word can have one or more options, your task is to return all words that can be formed. Letters with multiple options are enclosed in curly braces (e.g., "{a,b,c}"). If no braces exist, the letter remains constant. The final list of words must be in lexicographical order.

Key Insights

  • Parse the input string into groups of characters, where each group is either a fixed letter or a sorted list of options from within braces.
  • Use backtracking (or BFS) to generate all possible combinations by exploring each option in the group sequentially.
  • Sorting the options in each group ensures that the final output is lexicographically sorted, or sorting the generated output at the end can also work.
  • The absence of nested braces simplifies the parsing process.

Space and Time Complexity

Time Complexity: O(n * k^n) in the worst case where n is the number of groups and k is the maximum number of options per group (exponential in the number of groups).
Space Complexity: O(n) for recursion stack and O(k^n * n) for storing the output combinations.

Solution

We first parse the given string into a list of groups. Each group is either a single character or a sorted list of characters extracted from within curly braces. Then, we use a backtracking algorithm to build each possible word by selecting one option from each group sequentially. Every complete word is added to the result list. Finally, the list is returned, which is inherently sorted if the groups were sorted during parsing.

Code Solutions

# Function to perform brace expansion
def braceExpansion(s):
    # List to hold groups of characters
    groups = []
    i = 0
    # Parse the input string into groups
    while i < len(s):
        if s[i] == '{':
            i += 1  # skip the opening brace
            temp = []
            # Collect characters until the closing brace
            while s[i] != '}':
                if s[i] != ',':
                    temp.append(s[i])
                i += 1
            groups.append(sorted(temp))  # sort options to maintain order
            i += 1  # skip the closing brace
        else:
            groups.append([s[i]])
            i += 1

    # List to store the complete words
    result = []
    
    # Backtracking function to build words
    def backtrack(index, path):
        # If path length equals number of groups, add the formed word to result
        if index == len(groups):
            result.append("".join(path))
            return
        # Iterate over each option in the current group
        for ch in groups[index]:
            path.append(ch)          # add the current character to the path
            backtrack(index + 1, path) # move on to the next group
            path.pop()               # remove the last character (backtrack)

    backtrack(0, [])
    return result

# Example usage:
print(braceExpansion("{a,b}c{d,e}f"))
← Back to All Questions