Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1188. Brace Expansion II

My accepted Python solution to LeetCode problem 1188, Brace Expansion II, running in 3ms.

  • Difficulty: Hard
  • Python
  • Runtime 3ms
  • Memory 17.5MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 3ms, memory 17.5MB, accepted 2025-12-29.

python
class Solution:
    def braceExpansionII(self, expression: str) -> List[str]:
        def parse(expr, i):
            # Returns (set of words, next index)
            result = set()
            current = {''}
            
            while i < len(expr):
                if expr[i] == '{':
                    # Parse the group inside braces
                    inner, i = parse(expr, i + 1)
                    # Concatenate current with inner
                    current = {c + w for c in current for w in inner}
                elif expr[i] == '}':
                    result.update(current)
                    return result, i + 1
                elif expr[i] == ',':
                    result.update(current)
                    current = {''}
                    i += 1
                else:
                    # Letter
                    current = {c + expr[i] for c in current}
                    i += 1
            
            result.update(current)
            return result, i
        
        result, _ = parse(expression, 0)
        return sorted(result)

Source