回溯算法-括号生成

Love The Way You Lie 2023-02-15 10:07 1阅读 0赞

[22.括号生成][22.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI_size_16_color_FFFFFF_t_70]  
思路：先用回溯算法生成所有可能的括号，再判断生成的括号是否为有效括号。  
对于有效括号的判断，leetcode也有一道专门的题，用栈辅助就可以很简单的解决。整体代码也没啥，就是回溯+有效括号的判断

class Solution:
        def generateParenthesis(self, n: int) -> List[str]:
            res = []
            arr = ['(', ')']
            length = 2 * n
            def is_valid(s):  #判断括号是否有效
                stack = []
                #从后向前遍历，遇到')'就加入栈中，遇到'('就弹出栈顶元素
                for i in range(length-1, -1, -1):
                    if s[i] == ')':
                        stack.append(')')
                    else:
                        if stack:
                            stack.pop()
                        else:
                            return False
                return False if stack else True  #如果是有效括号，栈最终肯定是空的
    
            def backtrace(s):  #回溯部分就没啥特别的，套模板
                if len(s) == length and is_valid(s): #终止条件
                    if not s in res:
                        res.append(s)
                for i in range(2):
                    if len(s + arr[i]) > length: #剪枝
                        break
                    s += arr[i]
                    backtrace(s)
                    s = s[:-1]
            backtrace('')
            return res

[22.]: https://leetcode-cn.com/problems/generate-parentheses/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020060422363217.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI=,size_16,color_FFFFFF,t_70