leetcode——22. 括号生成

动态规划。。。

有待优化。。。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n==0:
            return ['']
        if n==1:
            return ['()']
        if n==2:
            return ['(())','()()']
        memo={}
        memo[0]=['']
        memo[1]=['()']
        memo[2]=['(())','()()']
        for i in range(3,n+1):
            memo[i]=[]
            for j in range(len(memo[i-1])):
                for k in range(1,(i-1)**2):
                    if memo[i-1][j][:k+1]+'()'+memo[i-1][j][k+1:] in memo[i]:
                        continue
                    else:
                        memo[i].append(memo[i-1][j][:k+1]+'()'+memo[i-1][j][k+1:])
        return memo[n]

执行用时 :288 ms, 在所有 python3 提交中击败了5.37%的用户

内存消耗 :13.8 MB, 在所有 python3 提交中击败了5.27%的用户

 

                                                                                ——2019.10.17