Brace Expansion

Medium

Stripe

3 views

Topics:

ArraysStringsRecursion

You are given a string s representing a list of words. Each letter in the word has 1 or more options.

If there is one option, the letter is represented by a single lowercase letter.
If there is more than one option, then curly braces delimit the options. For example, "{a,b,c}" represents options ["a", "b", "c"].

For example, if s = "{a,b,c}d{e,f}" then the corresponding options are ["a", "b", "c"] for the first part, and ["e", "f"] for the second part.

You are to expand the string into a list of words. The order of each word must be the same as in the original string. Return the list of all possible expanded words, sorted lexicographically.

Example 1:

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

Example 2:

Input: s = "abcd"
Output: ["abcd"]

Constraints:

1 <= s.length <= 50
s consists of curly brackets '{}', comma ',', and lowercase English letters.
s is guaranteed to be valid such that:
- There are no nested curly brackets.
- All characters inside a pair of consecutive opening and ending curly brackets are different.

Try coding it in LeetCode

Brace Expansion

Medium

Stripe

3 views

Topics:

ArraysStringsRecursion

You are given a string s representing a list of words. Each letter in the word has 1 or more options.

If there is one option, the letter is represented by a single lowercase letter.
If there is more than one option, then curly braces delimit the options. For example, "{a,b,c}" represents options ["a", "b", "c"].

For example, if s = "{a,b,c}d{e,f}" then the corresponding options are ["a", "b", "c"] for the first part, and ["e", "f"] for the second part.

You are to expand the string into a list of words. The order of each word must be the same as in the original string. Return the list of all possible expanded words, sorted lexicographically.

Example 1:

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

Example 2:

Input: s = "abcd"
Output: ["abcd"]

Constraints:

1 <= s.length <= 50
s consists of curly brackets '{}', comma ',', and lowercase English letters.
s is guaranteed to be valid such that:
- There are no nested curly brackets.
- All characters inside a pair of consecutive opening and ending curly brackets are different.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string contain nested braces or only single-level braces?
Can the options within the braces contain any characters other than lowercase English letters? For example, can they contain numbers or special characters?
If the input string is empty or contains no braces, what should the output be?
Is the order of options within a brace significant, or can I process them in any order?
If the expansion results in the same word multiple times, should the output list contain duplicates, or should it be a list of unique words?

Brute Force Solution

Approach

The problem asks us to expand a string containing brace-enclosed options. The brute force approach generates every single possible combination by systematically exploring all choices at each brace group. This guarantees we find all valid expansions.

Here's how the algorithm would work step-by-step:

Start reading the input string from left to right.
If you find a brace, say '{a,b,c}', consider each option (a, b, and c) one at a time.
For each option, create a new string by replacing the brace group with that option.
Continue this process for the rest of the string. If you encounter another brace group, again consider each option in the group to expand each partial string.
Keep doing this until there are no more braces left in any of the created strings.
The final set of strings without any braces represents all the possible expanded forms of the original string.
If the problem asks for the result to be ordered, sort the resulting list of strings.

Code Implementation

def brace_expansion_brute_force(expression):
    possible_expansions = [expression]

    while True:
        new_possible_expansions = []
        found_brace = False

        for current_expansion in possible_expansions:
            brace_start_index = current_expansion.find('{')

            if brace_start_index != -1:
                found_brace = True
                brace_end_index = current_expansion.find('}', brace_start_index)
                options_string = current_expansion[brace_start_index + 1:brace_end_index]
                options = options_string.split(',')

                # Iterate through options to create new strings
                for option in options:
                    new_expansion = current_expansion[:brace_start_index] + option + current_expansion[brace_end_index + 1:]
                    new_possible_expansions.append(new_expansion)
            else:
                new_possible_expansions.append(current_expansion)

        possible_expansions = new_possible_expansions

        # If no braces were found, we're done
        if not found_brace:
            break

    possible_expansions.sort()
    return possible_expansions

Big(O) Analysis

Time Complexity

O(2^n) – The time complexity is exponential because each brace expansion can potentially double the number of strings we need to process. Specifically, 'n' represents the number of brace groups. Each brace group multiplies the possibilities by the number of options within it. In the worst-case scenario, each brace group contains a constant number of options (e.g., 2), which leads to a branching factor of 2 for each brace group leading to 2 * 2 * ... * 2 (n times), hence approximately 2^n possible expansions to explore. Therefore, the overall time complexity is O(2^n) where n is the number of brace groups.

Space Complexity

O(M^K) – The auxiliary space is dominated by the storage of the intermediate and final expanded strings. In the worst-case scenario, where we have K brace groups, each with M options, the algorithm generates M^K possible strings. Storing these strings requires space proportional to M^K, where each string's length contributes a constant factor which is suppressed by the Big O notation. Therefore, the space complexity is O(M^K), where M is the maximum number of options within a brace group and K is the number of brace groups.

Optimal Solution

Approach

The best way to expand braces is to break down the problem into smaller, manageable parts. We'll use a technique called recursion to handle nested brace expansions, and build the final result step-by-step.

Here's how the algorithm would work step-by-step:

Identify the outermost set of braces in the input string.
If there are no braces, return the input string as is because there is nothing to expand.
If braces are found, split the string into sections based on the commas inside the braces.
Expand each section recursively by calling the same process on each part.
Combine the results from expanding each section. The final expanded result is the combination of each section added to each other.
If there are nested braces, the recursive calls will handle the inner expansions first, working from the inside out.
Continue expanding all the brace occurrences until the final string is produced.

Code Implementation

def brace_expansion(expression):
    # Find the first occurrence of an opening brace.
    start_brace_index = expression.find('{')
    if start_brace_index == -1:
        return [expression]

    # Find the matching closing brace.
    brace_level = 0
    end_brace_index = -1
    for index, char in enumerate(expression):
        if char == '{':
            brace_level += 1
        elif char == '}':
            brace_level -= 1
            if brace_level == 0:
                end_brace_index = index
                break

    # Extract the content inside the braces.
    options_string = expression[start_brace_index + 1:end_brace_index]

    # Split the options by comma.
    options = options_string.split(',')
    prefix = expression[:start_brace_index]
    suffix = expression[end_brace_index + 1:]

    expanded_options = []
    # Recursively expand each option.
    for option in options:
        expanded_prefix = brace_expansion(prefix)
        expanded_suffix = brace_expansion(suffix)

        # Combine all possibilities.
        for pre in expanded_prefix:
            for suf in expanded_suffix:
                expanded_options.append(pre + option + suf)

    return sorted(expanded_options)

Big(O) Analysis

Time Complexity

O(m^n) – Let n be the maximum nesting depth of the braces and m be the maximum number of comma-separated options within a single set of braces. In the worst-case scenario, each brace expansion multiplies the number of strings to generate. At each level of recursion (up to depth n), we might have to process 'm' possible expansions. Since the expansions can multiply at each level, the total number of expansions in the worst case grows exponentially. Therefore, the overall time complexity is O(m^n), where m represents choices within each expansion and n is the maximum depth of nested braces.

Space Complexity

O(N) – The algorithm's space complexity is dominated by the recursion depth. In the worst-case scenario, where braces are heavily nested, the recursion can go as deep as the number of characters in the input string, denoted as N. Each recursive call adds a new frame to the call stack, consuming memory. Therefore, the auxiliary space used by the recursion stack is proportional to N, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty list immediately as there's nothing to expand.
Input string with no braces	Return a list containing the input string itself, treating it as a single literal.
Input string with nested braces	Handle nested braces recursively or iteratively, ensuring correct order of expansion.
Input string with empty brace sets e.g., '{a,}'	Treat an empty brace set as a valid option contributing to the possible expansions.
Input string with consecutive brace sets e.g., '{a,b}{c,d}'	Expand each brace set independently and then concatenate results.
Input string with duplicate options within a brace set e.g., '{a,a,b}'	Treat duplicate options as distinct and expand accordingly, resulting in potentially duplicate words in the output, which are then sorted and made unique.
Input string with leading or trailing spaces	Trim the input string before processing to avoid unexpected characters affecting expansion.
Input string with extremely deep nesting leading to a combinatorial explosion	The exponential complexity is inherent to the problem, but it's important to test for stack overflow issues with deep recursion and consider iterative approaches for potentially large inputs.