<p>Under the grammar given below, strings can represent a set of lowercase words. Let&nbsp;<code>R(expr)</code>&nbsp;denote the set of words the expression represents.</p>

<p>The grammar can best be understood through simple examples:</p>

<ul>
	<li>Single letters represent a singleton set containing that word.
	<ul>
		<li><code>R(&quot;a&quot;) = {&quot;a&quot;}</code></li>
		<li><code>R(&quot;w&quot;) = {&quot;w&quot;}</code></li>
	</ul>
	</li>
	<li>When we take a comma-delimited list of two or more expressions, we take the union of possibilities.
	<ul>
		<li><code>R(&quot;{a,b,c}&quot;) = {&quot;a&quot;,&quot;b&quot;,&quot;c&quot;}</code></li>
		<li><code>R(&quot;{{a,b},{b,c}}&quot;) = {&quot;a&quot;,&quot;b&quot;,&quot;c&quot;}</code> (notice the final set only contains each word at most once)</li>
	</ul>
	</li>
	<li>When we concatenate two expressions, we take the set of possible concatenations between two words where the first word comes from the first expression and the second word comes from the second expression.
	<ul>
		<li><code>R(&quot;{a,b}{c,d}&quot;) = {&quot;ac&quot;,&quot;ad&quot;,&quot;bc&quot;,&quot;bd&quot;}</code></li>
		<li><code>R(&quot;a{b,c}{d,e}f{g,h}&quot;) = {&quot;abdfg&quot;, &quot;abdfh&quot;, &quot;abefg&quot;, &quot;abefh&quot;, &quot;acdfg&quot;, &quot;acdfh&quot;, &quot;acefg&quot;, &quot;acefh&quot;}</code></li>
	</ul>
	</li>
</ul>

<p>Formally, the three rules for our grammar:</p>

<ul>
	<li>For every lowercase letter <code>x</code>, we have <code>R(x) = {x}</code>.</li>
	<li>For expressions <code>e<sub>1</sub>, e<sub>2</sub>, ... , e<sub>k</sub></code> with <code>k &gt;= 2</code>, we have <code>R({e<sub>1</sub>, e<sub>2</sub>, ...}) = R(e<sub>1</sub>) &cup; R(e<sub>2</sub>) &cup; ...</code></li>
	<li>For expressions <code>e<sub>1</sub></code> and <code>e<sub>2</sub></code>, we have <code>R(e<sub>1</sub> + e<sub>2</sub>) = {a + b for (a, b) in R(e<sub>1</sub>) &times; R(e<sub>2</sub>)}</code>, where <code>+</code> denotes concatenation, and <code>&times;</code> denotes the cartesian product.</li>
</ul>

<p>Given an expression representing a set of words under the given grammar, return <em>the sorted list of words that the expression represents</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> expression = &quot;{a,b}{c,{d,e}}&quot;
<strong>Output:</strong> [&quot;ac&quot;,&quot;ad&quot;,&quot;ae&quot;,&quot;bc&quot;,&quot;bd&quot;,&quot;be&quot;]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> expression = &quot;{{a,z},a{b,c},{ab,z}}&quot;
<strong>Output:</strong> [&quot;a&quot;,&quot;ab&quot;,&quot;ac&quot;,&quot;z&quot;]
<strong>Explanation:</strong> Each distinct word is written only once in the final answer.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= expression.length &lt;= 60</code></li>
	<li><code>expression[i]</code> consists of <code>&#39;{&#39;</code>, <code>&#39;}&#39;</code>, <code>&#39;,&#39;</code>or lowercase English letters.</li>
	<li>The given&nbsp;<code>expression</code>&nbsp;represents a set of words based on the grammar given in the description.</li>
</ul>

class Solution:
    def braceExpansionII(self, expression: str) -> List[str]:
        # The main idea is to parse the expression recursively, handling union and concatenation,
        # while managing nested braces using a stack.

        # Initialize a stack to handle nested braces
        stack = []
        # 'res_set' will store the union of sets at the current level
        res_set = set()
        # 'curr_set' will store the current set of strings being built
        curr_set = set()

        i = 0  # Pointer to traverse the expression
        while i < len(expression):
            char = expression[i]
            
            if char == '{':
                # Start a new level for nested braces
                # Push the current state onto the stack
                stack.append((res_set, curr_set))
                # Reset 'res_set' and 'curr_set' for the new level
                res_set, curr_set = set(), set()
                i += 1

            elif char == '}':
                # End of the current level, time to combine with previous level
                # Union the current 'res_set' and 'curr_set' to get all strings at this level
                combined = res_set | curr_set
                # Pop the previous state from the stack
                prev_res_set, prev_curr_set = stack.pop()
                # If there are strings in the previous 'curr_set', concatenate them with 'combined'
                if prev_curr_set:
                    curr_set = set(p + c for p in prev_curr_set for c in combined)
                else:
                    curr_set = combined
                # Restore 'res_set' to the previous level's 'res_set'
                res_set = prev_res_set
                i += 1

            elif char == ',':
                # Comma indicates a union at the current level
                # Add 'curr_set' to 'res_set' to perform the union operation
                res_set |= curr_set
                # Reset 'curr_set' for the next group of strings
                curr_set = set()
                i += 1

            elif char.isalpha():
                # Build the string by concatenating consecutive letters
                # This handles multi-letter strings without additional loops
                j = i
                while i < len(expression) and expression[i].isalpha():
                    i += 1
                word = expression[j:i]
                # If 'curr_set' is not empty, concatenate 'word' with each string in 'curr_set'
                if curr_set:
                    curr_set = set(s + word for s in curr_set)
                else:
                    # Otherwise, initialize 'curr_set' with 'word'
                    curr_set = {word}

            else:
                # Skip any other characters (should not occur in valid expressions)
                i += 1

        # After processing the entire expression, combine 'res_set' and 'curr_set'
        final_set = res_set | curr_set
        # Return the sorted list of unique strings as per problem requirements
        return sorted(final_set)

17000