[LeetCode][python3]0022. Generate Parentheses

Start the Journey
N2I -2020.07.04

1. My first Solution

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n==0:
            return []
        ans=[]
        cur_str=""
        self.adder(ans,n,n,cur_str)
        return ans
        
        
    def adder(self,ans,l,r,cur_str):
        if r==0:
            ans.append(cur_str)
            return
        if l==r:
            self.adder(ans,l-1,r,cur_str+"(")
        else:
            self.adder(ans,l,r-1,cur_str+")")
            if l>0:
                self.adder(ans,l-1,r,cur_str+"(")

Explanation:

This is a recursive solution of this problem. The l and r is counting the amount of left and right parentheses. The rule is if the amount of l==r, there is only one possibility to extend the string. Otherwise there are two possibilities to extend the string. After the string extending complete, add it to the list.

2. A clean Solution

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = ["()"]
        for i in range(n - 1):
            res = set([x[:i] + "()" + x[i:] for x in res for i in range(len(x))])
        return res

Explanation:

A cool way to code it in python. This makes the code very clean.