【LeetCode】22. bracket-generating

1 subject

2 thought

Use deep search
There are two choices at a time , Push , Out of the stack . Then judge whether the string result is reasonable .
n Indicates the logarithm of the production bracket

3 Code

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

    #  Determine whether stack brackets match 
    def judge(self,string):
        left = 0
        right = 0
        for s in string:
            if s == "(":
                left += 1
            else:
                if left >0: #  Description of inventory 
                    left -=1
                else:
                    return False
        return True

    # left  Indicates the number of left parentheses ,right Indicates the number of right parentheses 
    def dfs(self,left,right,res,tmp):
        if left == 0 and right ==0: #  It's all over 
            if self.judge(tmp):
                res.append(copy.deepcopy("".join(tmp)))
            return 
        #  There are two choices every time , discharge left Let's go 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()