NeetCode #515LC-1087MediumBacktrackingNC Algo100
← Back to All Problems#515 · #1087 · Brace Expansion(花括号展开)
📌 Problem Statement & Constraints
You are given a string
expression representing a brace expansion, e.g. "{a,b}{c,{d,e}}". Return all words generated by the expansion, sorted in lexicographic order without duplicates. Constraints: 1 <= expression.length <= 60; the expression consists of lowercase letters, {, } and ,.💡 Core Algorithmic Approaches
- Parse recursively:
parse(i)returns the set of strings produced by the sub-expression starting ati, plus the next index. - Maintain
currentas the product accumulator for the current comma-separated group, andresultas the union of completed groups. - On
{, recurse and take the Cartesian product withcurrent. On,, foldcurrentintoresultand reset it. On}, fold and return. - Using sets throughout makes deduplication automatic, and sorting at the end gives the required order.
💻 Benchmark Python3 Implementation
class Solution:
def braceExpansionII(self, expression: str) -> List[str]:
def parse(i: int):
"""Return (set of expansions, next index)."""
result = set()
current = {""} # product accumulator for this group
while i < len(expression):
ch = expression[i]
if ch == "{":
sub, i = parse(i + 1)
# Cartesian product with the accumulated prefix
current = {a + b for a in current for b in sub}
elif ch == "}":
result |= current
return result, i + 1 # caller resumes after '}'
elif ch == ",":
result |= current # one alternative finished
current = {""}
else:
j = i
while j < len(expression) and expression[j].isalpha():
j += 1
word = expression[i:j] # a literal run
current = {a + word for a in current}
i = j - 1 # the outer i += 1 advances past it
i += 1
result |= current
return result, i
res, _ = parse(0)
return sorted(res)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(total characters * number of expansions): the product steps dominate.
💾 Space Complexity
O(number of expansions) for the sets.
⚠️ Interview Pitfalls & Follow-ups
- Treating the expression as a flat split on
,and{}: nesting and concatenation both matter. - Building the product after the whole group instead of incrementally: concatenation inside a group requires the running product.
- Forgetting to sort and deduplicate: the result must be sorted and free of duplicates, which the set plus final sort provides.
- Returning the index without skipping the
}: the caller would re-parse the closing brace.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.