0022. Generate Parentheses

Medium | String + DP | 28 ms (95.96%), 14.5 MB (87.81%)

❓ Problem Statement

Source: LeetCode - Generate Parentheses GitHub: Solution / Performance

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

✍🏻 Constraints & Example

Constraints:

• 1 <= n <= 8

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Input: n = 1
Output: ["()"]

💡 Ideas

We generate new combinations of well-formed parentheses based on previous iteration's results. Thus, it is a DP question.

Pattern 1: Add outer parenthesis by iterating previous results

dp[i] = set(['(' + x + ')' for x in dp[i-1]])

Pattern 2: Try all orders for all previous results and then perform set union.

# DP table has dp[1], dp[2], dp[3] and now compute for dp[4] (i=4)
# the following nested for loops will do: 
#     dp[i] |= set([x + y for x in dp[1] for y in dp[3]])
#     dp[i] |= set([x + y for x in dp[2] for y in dp[2]])
#     dp[i] |= set([x + y for x in dp[3] for y in dp[1]])

for j in range(1, i):
    dp[i] |= set([x + y for x in dp[j] for y in dp[i-j]])

🤖 Python3 (DP)

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        
        # ==================================================
        #  Dynamic Programming                             =
        # ==================================================
    
        dp = {1: set(['()']), 2: set(['(())', '()()'])}
        
        # (base case)
        if n == 1 or n == 2: return dp[n]
        
        for i in range(3, n+1):
            # pattern 1: outer parenthesis + subproblem with length - 1
            dp[i] = set(['(' + x + ')' for x in dp[i-1]])
            
            # pattern 2: dp[i] is formed by dp[j] + dp[i-j]
            for j in range(1, i):
                # perform set union on combinations of elements in dp[j] and dp[i-j]
                dp[i] |= set([x + y for x in dp[j] for y in dp[i-j]])
        
        return list(dp[n])

🤖 Python3 (Set)

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        # (base case)
        if n == 1: return ['()']
        
        # ==================================================
        #  String + Set                                    =
        # ==================================================
        
        ans = ['()']
        
        for _ in range(n-1):
            result = set()

            # insert '()' in each index of string
            # then using SET JOIN to combine without duplicate items
            for string in ans : result |= self.insertParenthesis( string )

            ans = result

        return ans
    
    def insertParenthesis(self, string) -> set:        
        ret = set()
        for i in range(len(string)) : ret.add(string[:i] + '()' + string[i:])
        return ret