Brace Expansion - Video Solutions
LeetCode 1087. Brace Expansion Explanation and Solution
Brace Expansion - Video Solution
Watch 10 video solutions for Brace Expansion, a medium level problem involving String, Backtracking, Breadth-First Search. This walkthrough by happygirlzt has 3,804 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 50sconsists of curly brackets'{}', commas',', and lowercase English letters.sis 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.
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. |