Brace Expansion — LeetCode 1087 Python Solution
MediumLeetCode PremiumStackBreadth-First SearchStringBacktrackingSorting
- Problem
- #1087
- Pattern
- Backtracking
- Reading time
- 5 min
- Source
- leetcode.com
The problem
You are given a string s representing a list of words. Each letter in the word has one or more options.
Example
- Input
- s = "{a,b}c{d,e}f"
- Output
- ["acdf","acef","bcdf","bcef"]
Python 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 ansComplexity
| Measure | Complexity |
|---|---|
| Time | Exponential (worst case) |
| Space | O(depth) auxiliary |
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 1087. Brace Expansion is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.
The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1087. Brace Expansion?
- LeetCode 1087. Brace Expansion is rated Medium on LeetCode.
- What topics does LeetCode 1087. Brace Expansion cover?
- LeetCode 1087. Brace Expansion is tagged Stack, Breadth-First Search, String, Backtracking and Sorting on LeetCode.
- Is LeetCode 1087. Brace Expansion a premium problem?
- Yes. LeetCode 1087. Brace Expansion is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.