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

Function shape:

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

Examples

Example 1:

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

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

All combinations: acdf, acef, bcdf, bcef.

Answer:

["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

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

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()