# LeetCode 1087: Brace Expansion

## Problem Restatement

We are given a string `s` representing a word with the following format:

- A single letter `c` means the set `{c}`.
- A brace expression `{a,b,c,...}` means choose one of the letters.
- Consecutive groups are concatenated.

Return all strings generated by the pattern in sorted order.

The official constraints state that `1 <= s.length <= 50`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Pattern string `s` |
| Output | Sorted list of all generated strings |

Function shape:

```python
def expand(s: str) -> list[str]:
    ...
```

## Examples

Example 1:

```python
s = "{a,b}c{d,e}f"
```

Groups: `{a,b}`, `c`, `{d,e}`, `f`.

All combinations: `acdf, acef, bcdf, bcef`.

Answer:

```python
["acdf","acef","bcdf","bcef"]
```

## Key Insight

Parse the pattern into groups (lists of characters). Then generate all combinations using backtracking or itertools.product.

## Algorithm

1. Parse `s` into groups. A `{...}` segment becomes a sorted list of choices. A single letter becomes a list with one character.
2. Use backtracking (or itertools.product) to generate all combinations.
3. Return sorted results.

## Edge Cases

- Mark nodes or cells as visited at enqueue/discovery time to avoid duplicate work.
- Return the failure value when the destination is unreachable.
- Check grid or graph boundaries before reading neighbors.

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```python
from itertools import product

class Solution:
    def expand(self, s: str) -> list[str]:
        groups = []
        i = 0
        while i < len(s):
            if s[i] == '{':
                j = s.index('}', i)
                groups.append(sorted(s[i+1:j].split(',')))
                i = j + 1
            else:
                groups.append([s[i]])
                i += 1

        return sorted("".join(combo) for combo in product(*groups))
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.expand("{a,b}c{d,e}f") == ["acdf","acef","bcdf","bcef"]
    assert s.expand("abcd") == ["abcd"]
    assert s.expand("{a,b,c}") == ["a","b","c"]

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---|---|
| Two brace groups | `["acdf","acef","bcdf","bcef"]` | 2×2 combinations |
| No braces | `["abcd"]` | Single string |
| Single brace | `["a","b","c"]` | Three choices |