【LeetCode】22. 括号生成

1 题目

2 思想

使用深搜
每次有两种选择，入栈，出栈。然后判断得到的字符串结果是否合理即可。
n表示生产括号的对数

3 代码

import copy
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        self.dfs(n,n,res,[])
        # print(res)
        # tmp = []
        # for i in res:
        # if self.judge(i):
        # tmp.append("".join(i))
        return res

    # 判断栈括号是否匹配
    def judge(self,string):
        left = 0
        right = 0
        for s in string:
            if s == "(":
                left += 1
            else:
                if left >0: # 说明有存货
                    left -=1
                else:
                    return False
        return True

    # left 表示左括号个数，right表示右括号个数
    def dfs(self,left,right,res,tmp):
        if left == 0 and right ==0: # 全部放完了
            if self.judge(tmp):
                res.append(copy.deepcopy("".join(tmp)))
            return 
        # 每次都有两种选择，放left还是放right?
        if left:
            tmp.append("(")
            self.dfs(left-1,right,res,tmp)
            tmp.pop()
        if right:
            tmp.append(")")
            self.dfs(left,right-1,res,tmp)
            tmp.pop()