1096.md

1096. Brace Expansion II

Solution 1

class Solution(object):
    def braceExpansionII(self, expression):
        """
        :type expression: str
        :rtype: List[str]
        """
        def dfs(exp):
            j = exp.find("}")
            if j == -1:
                ans.add(exp)
                return
            i = exp.rfind("{", 0, j)
            a, c = exp[:i], exp[j + 1:]
            for b in exp[i + 1: j].split(","):
                dfs(a + b + c)

        ans = set()
        dfs(expression)
        return sorted(ans)