1087. Brace Expansion - Solution & Explanation

Q: Is Brace Expansion easy or hard?

Brace Expansion is generally rated medium difficulty. The parsing step is straightforward, but recognizing that the problem reduces to combination generation using backtracking or BFS is the key insight.

Q: Brace Expansion Python/Java solution

Python and Java implementations typically parse the expression into groups and use backtracking to generate results. Python solutions often use recursion with list accumulation, while Java versions use a StringBuilder for efficient string construction.

Q: How to solve Brace Expansion in O(n)?

A strict O(n) solution is not possible because the output itself may contain many strings. The optimal approach runs in O(R * L), proportional to the total size of the generated output. Backtracking or BFS both achieve this optimal bound.

Q: What is the best approach for Brace Expansion?

Backtracking is the most common solution. Parse the expression into segments and recursively build strings by choosing one character from each group. This directly generates every valid combination while keeping results in lexicographic order if each group is sorted.

Q: Is Brace Expansion asked at Google/Amazon/Meta?

Brace-style expansion problems appear in interviews at large tech companies because they test recursion, parsing, and combinatorial generation. Variants of this problem have appeared in interviews at companies like Google and Amazon.

Q: What data structure is used in Brace Expansion?

The main structures are arrays or lists to store characters in each brace group, plus either a recursion stack (backtracking) or a queue for BFS. Strings or character buffers are used to build the final combinations.

Q: What is the time complexity of Brace Expansion?

The time complexity is O(R * L), where R is the number of generated strings and L is the length of each string. Every character of every resulting string must be constructed at least once, which dominates the runtime.

The problem

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

If there is one option, the letter is represented as is.
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}", the first character is always 'a', but the second character can be 'b' or 'c'. The original list is ["ab", "ac"].

Return all words that can be formed in this manner, sorted in lexicographical order.

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 '{}', commas ',', and lowercase English letters.
s is guaranteed to be a valid input.
There are no nested curly brackets.
All characters inside a pair of consecutive opening and ending curly brackets are different.

Approach overview

Problem Overview: Given a string containing groups like {a,b}, generate every possible string by choosing one character from each brace group. The final output must be sorted lexicographically.

Approach 1: Backtracking Expansion (O(R * L) time, O(R * L) space)

Parse the string and treat each brace group as a list of candidate characters. Regular characters behave like groups with a single option. Then use backtracking to build the result string one position at a time. At each step, iterate through the available characters for the current segment and append one to the growing path, then recurse to the next segment.

The key insight is that the problem is simply generating combinations across multiple character sets. Sorting each brace group before exploring guarantees the final results appear in lexicographic order without an extra sort. If the final number of generated strings is R and each string length is L, the algorithm runs in O(R * L) time because each character of each result is constructed once.

This approach fits naturally with recursive search patterns used in many string construction problems. The recursion depth equals the number of segments in the parsed expression.

Approach 2: Breadth-First Expansion (O(R * L) time, O(R * L) space)

You can also solve the problem using a queue and Breadth-First Search. Start with an empty string in the queue. For each parsed segment of the expression, expand every partial string currently in the queue by appending each possible character from that segment.

This produces the next layer of partial results until all segments are processed. Each level represents choosing a character from the next group. The final queue contains every valid expansion.

The BFS version avoids recursion and is often easier to reason about when thinking of the problem as layer-by-layer string construction. The time complexity is still O(R * L), since every generated string must be created explicitly.

Recommended for interviews: The backtracking approach is typically expected. It clearly shows you understand recursive combination generation and pruning patterns. Mentioning BFS as an alternative demonstrates deeper understanding of state expansion problems.

Solution

Python

class Solution:
    def expand(self, s: str) -> List[str]:
        def convert(s):
            if not s:
                return
            if s[0] == '{':
                j = s.find('}')
                items.append(s[1:j].split(','))
                convert(s[j + 1 :])
            else:
                j = s.find('{')
                if j != -1:
                    items.append(s[:j].split(','))
                    convert(s[j:])
                else:
                    items.append(s.split(','))

        def dfs(i, t):
            if i == len(items):
                ans.append(''.join(t))
                return
            for c in items[i]:
                t.append(c)
                dfs(i + 1, t)
                t.pop()

        items = []
        convert(s)
        ans = []
        dfs(0, [])
        ans.sort()
        return ans

Java

class Solution {
    private List<String> ans;
    private List<String[]> items;

    public String[] expand(String s) {
        ans = new ArrayList<>();
        items = new ArrayList<>();
        convert(s);
        dfs(0, new ArrayList<>());
        Collections.sort(ans);
        return ans.toArray(new String[0]);
    }

    private void convert(String s) {
        if ("".equals(s)) {
            return;
        }
        if (s.charAt(0) == '{') {
            int j = s.indexOf("}");
            items.add(s.substring(1, j).split(","));
            convert(s.substring(j + 1));
        } else {
            int j = s.indexOf("{");
            if (j != -1) {
                items.add(s.substring(0, j).split(","));
                convert(s.substring(j));
            } else {
                items.add(s.split(","));
            }
        }
    }

    private void dfs(int i, List<String> t) {
        if (i == items.size()) {
            ans.add(String.join("", t));
            return;
        }
        for (String c : items.get(i)) {
            t.add(c);
            dfs(i + 1, t);
            t.remove(t.size() - 1);
        }
    }
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Backtracking Expansion	O(R * L)	O(R * L)	Best general solution. Clean recursive generation and easy lexicographic ordering.
Breadth-First Expansion (Queue)	O(R * L)	O(R * L)	Useful when avoiding recursion or when modeling the problem as level-by-level state expansion.

Frequently asked questions

Is Brace Expansion easy or hard?

Brace Expansion is generally rated medium difficulty. The parsing step is straightforward, but recognizing that the problem reduces to combination generation using backtracking or BFS is the key insight.

Brace Expansion Python/Java solution

Python and Java implementations typically parse the expression into groups and use backtracking to generate results. Python solutions often use recursion with list accumulation, while Java versions use a StringBuilder for efficient string construction.

How to solve Brace Expansion in O(n)?

A strict O(n) solution is not possible because the output itself may contain many strings. The optimal approach runs in O(R * L), proportional to the total size of the generated output. Backtracking or BFS both achieve this optimal bound.

What is the best approach for Brace Expansion?

Backtracking is the most common solution. Parse the expression into segments and recursively build strings by choosing one character from each group. This directly generates every valid combination while keeping results in lexicographic order if each group is sorted.

Is Brace Expansion asked at Google/Amazon/Meta?

Brace-style expansion problems appear in interviews at large tech companies because they test recursion, parsing, and combinatorial generation. Variants of this problem have appeared in interviews at companies like Google and Amazon.

What data structure is used in Brace Expansion?

The main structures are arrays or lists to store characters in each brace group, plus either a recursion stack (backtracking) or a queue for BFS. Strings or character buffers are used to build the final combinations.

What is the time complexity of Brace Expansion?

The time complexity is O(R * L), where R is the number of generated strings and L is the length of each string. Every character of every resulting string must be constructed at least once, which dominates the runtime.

Brace Expansion solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Brace Expansion solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems