Problem statement

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

Solution 1

The idea is the following: let us try to solve this problem recursively: given correct substring dfs return all strings generated for this substring. What any correct substring will look like is the following:

{..}{..}, {..}{..}{..}, x, abc, {..}, a{..}b

Here as small parts we can have either product of brackets expressions or one bracket expression or some letters. What actually matters is we need to find comma symbol just after we have balance equal to 0.

  1. If we found it we can separate problem into two subproblems.
  2. If we did not found it it means that we have product so we will look for first closing bracket after which balance is zero.
  3. If we do not found it either, it means that we have {..}, where the last bracket is corresponding to the first.

Complexity

Time and space complexity potentially is O(2^n), because it is number of potential words.

Code

class Solution:
    def braceExpansionII(self, E):
        def dfs(beg, end):
            if beg == end: return set(E[beg])
            bal, cands = 0, defaultdict(list)
            
            for i in range(beg, end + 1): 
                bal += (E[i] == "{") - (E[i] == "}")
                if bal == 0 and i + 1 <= end: cands[E[i+1] == ","].append(i)
                    
            if cands[1]:
                return dfs(beg, cands[1][0]) | dfs(cands[1][0]+2, end)
            
            if cands[0]:
                return set(a+b for a,b in product(dfs(beg, cands[0][0]), dfs(cands[0][0] + 1, end)))

            return dfs(beg + 1, end - 1)
            
        return sorted(dfs(0, len(E) - 1))

Solution 2

There is also solution similar to Basic Calculators I, II, III solutions: the idea is to use the stack of monomials.

Complexity

It is O(2^n) for time and space.

Code

class Solution:
    def braceExpansionII(self, E):
        stack, union, prod = [], [], [""]
        for c in E:
            if c.isalpha():
                prod = [v + c for v in prod]
            elif c == '{':
                stack.append(union)
                stack.append(prod)
                union, prod = [], [""]
            elif c == '}':
                pre_prod, pre_union = stack.pop(), stack.pop()
                prod = [p + v for p, v in product(pre_prod, union + prod)]
                union = pre_union
            elif c == ',':
                union += prod
                prod = [""]
                
        return sorted(set(union + prod))