Skip to main content
Talentd

Brace Expansion - Solution & Explanation

MediumPremiumFree on FleetCodeStringBacktrackingBreadth-First Search4 min readAsked at: Apple, DoorDash, Google +3
Practice this problem

Problem Statement

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

Code

PythonJava

Python

Java

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking ExpansionO(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.

Video Solution

LeetCode 1087. Brace Expansion Explanation and Solution • happygirlzt • 3,804 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Brace Expansion with our built-in code editor and test cases.

Practice on FleetCode
Previous

Brace Expansion II

Next

Decode String