Problem statement

https://leetcode.com/problems/brace-expansion/

Solution

We can split string by brackets and then further split it by commas, because we are given that we do not have nested brackets. Then we can use functionality of product.

Complexity

Time complexity to create t is O(n), but then we need to create answer as well. Potentially it can be upto O(2^(n/5)) for the case with two letters in each brackets

Code

class Solution:
    def expand(self, s):
        t = []
        parts = s.replace("{", "}").split("}")
        for part in parts:
            if not part: continue
            t.append(sorted(part.split(",")))

        return ["".join(x) for x in product(*t)]