## The problem [Brace Expansion II](https://leetcode.com/problems/brace-expansion-ii/) hands me an expression built from lowercase letters, curly braces, and commas, and asks for every distinct word it can produce, sorted. The grammar is compact but recursive: braces nest inside braces, and a comma at the top level means one thing while a comma inside a brace group means another. That nesting is the whole difficulty — a single left-to-right scan can't see the structure. Two operations define the language: - **Union** — `{a,b}` is "a or b". Commas separate alternatives. - **Concatenation** — writing units side by side, like `{a,b}{c,d}`, glues every choice on the left to every choice on the right: `ac, ad, bc, bd`. And these compose to any depth: `{a,b}{c,{d,e}}` produces `ac, ad, ae, bc, bd, be`. ## Everything is a set of strings The clean way to think about it: every syntactic unit *produces a set of strings*. - A letter `a` produces `{"a"}`. - A brace group `{...}` produces whatever the expression inside produces. - Concatenating two units is the pairwise product: each string on the left joined to each string on the right. - A comma union is the set union of its parts. Because the answer has to be sorted and free of duplicates, I hold everything in a `std::set`. Sorting and dedup come for free — `{{a,z},a{b,c},{ab,z}}` collapses `ab` from two different branches into one entry, and a set handles that without a second thought. ## Recursive descent, one function per rule The grammar has three levels, so I write three mutually recursive functions over a shared cursor `pos`: ```cpp class Solution { public: string expr; size_t pos = 0; // union: term (',' term)* set parseUnion() { set res = parseConcat(); while (pos < expr.size() && expr[pos] == ',') { ++pos; // consume ',' set nxt = parseConcat(); res.insert(nxt.begin(), nxt.end()); } return res; } // concatenation of factors until ',' '}' or end set parseConcat() { set res = {""}; while (pos < expr.size() && expr[pos] != ',' && expr[pos] != '}') { set factor; if (expr[pos] == '{') { ++pos; // consume '{' factor = parseUnion(); ++pos; // consume '}' } else { factor = { string(1, expr[pos]) }; ++pos; } set merged; for (const string& a : res) for (const string& b : factor) merged.insert(a + b); res.swap(merged); } return res; } vector braceExpansionII(string expression) { expr = expression; pos = 0; set s = parseUnion(); return vector(s.begin(), s.end()); } }; ``` `parseUnion` reads one concatenation, then keeps consuming a comma and unioning the next concatenation as long as it sees commas. `parseConcat` seeds its result with `{""}` and, for each factor until it hits a delimiter, multiplies the running set by that factor's set. A factor is either a brace group — consume `{`, recurse into `parseUnion`, consume `}` — or a single letter. That empty-string seed is load-bearing: it makes the first factor pass through unchanged (`"" + "a" = "a"`) and lets every later factor extend what came before. ## The cursor hand-off is the only place it bites The one invariant that keeps this correct: **every function leaves `pos` just past what it consumed.** `parseConcat` stops *without* eating the comma or brace that ended it, so its caller decides what that delimiter means — `parseUnion` treats a comma as "another alternative," and a brace group's caller treats `}` as "close me." Get those hand-offs consistent and arbitrary nesting just works, because `parseConcat` calls `parseUnion` calls `parseConcat` all the way down. I traced it against a few inputs before trusting it: - `{a,b}{c,{d,e}}` → `ac ad ae bc bd be` - `{{a,z},a{b,c},{ab,z}}` → `a ab ac z` - `{a,b}{c,d}` → `ac ad bc bd` All matched. ## Cost Each character is consumed exactly once by the parser, so the parse itself is linear in the input length. The real work is the Cartesian products and set inserts: if the answer has `m` distinct words up to length `L`, that's about `O(m · L · log m)`. With the expression capped at 50 characters, that's tiny — the judge clocked it at 11 ms. The takeaway I keep from this one: when a "string manipulation" problem is actually a small grammar, stop trying to scan it and just write the recursive-descent parser. Naming the grammar rules turns a fiddly problem into three short, obviously-correct functions.