[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.

HI I’m N2I. Now a Computer Science and Engineering Student of NCHU in Taiwan. Check out more about me in https://nzi2020.blogspot.com/