⚡Flashcard Drill➔
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

  1. Parse recursively: parse(i) returns the set of strings produced by the sub-expression starting at i, plus the next index.
  2. Maintain current as the product accumulator for the current comma-separated group, and result as the union of completed groups.
  3. On {, recurse and take the Cartesian product with current. On ,, fold current into result and reset it. On }, fold and return.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems