提示：如果本文对您有帮助，欢迎点赞支持！

目录

前言

一、判断一个括号字符串是否有效

二、括号字符串无效的位置

三、回溯生成多个括号字符串

前言

括号系列算法问题是经典的面试高频题，括号系列题目的核心考点就是用栈和DFS 算法。对于括号问题，要明白如下2条规律：

一个「合法」的括号字符串一定满足如下2个条件：

1、括号字符串中的左括号数量一定等于右括号数量**。

2、对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len(p)都有：子串 p[0..i] 中左括号的数量都大于或等于右括号的数量。

 借助栈，我们可以查找一个合法字符串中的所有括号不合法位置，这是我们解决括号问题总结出来的模板：

// 用栈模拟一遍，标记处所有无法匹配括号的位置
// 例如 ")()((())"的mark为[1, 0, 0, 1, 0, 0, 0, 0]
stack stk;
vector mark(s.length(),0);
for(int i=0;i 
 阅读完本文，你将可以提交如下LeetCode题目：
 
类型
LeetCode题目
 
判断一个括号字符串是否有效
 
 
20. 有效的括号（简单难度）
 
 
1614. 括号的最大嵌套深度（简单难度）
 
 
括号字符串无效的位置
 
 
1249. 移除无效的括号（中等难度）
 
 
32. 最长有效括号（困难难度）
 
 
678. 有效的括号字符串（中等难度）
 
 
回溯生成多个括号字符串
 
 
22. 括号生成（中等难度）
 
 
剑指 Offer II 085. 生成匹配的括号（中等难度）
 
 
面试题 08.09. 括号（中等难度）
 
 
301. 删除无效的括号（困难难度）
 

一、判断一个括号字符串是否有效 
给定一个包含若干个左右括号的字符串，例如“()))()()()”,判断其是否有效，有效是指：左括号后必须用相同类型的右括号闭合， 左括号必须以正确的顺序闭合。
 
 bool isValid(const string & s) {
     int cnt = 0;
     // 判断括号字符串是否合法
     for (int i = 0; i < s.size(); i++) {
         if (s[i] == '(') cnt++;// 遇到左括号计数+1
         else if (cnt>0&&s[i] == ')') cnt--;// 遇到右括号且计数>0,说明可以消耗一个计数
         else return false;
     }
     return cnt == 0;//如果计数=0，说明左括号全部被匹配，否则剩余左括号
 }
 
 
 
20. 有效的括号（简单难度）
 
 给定一个包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 
该题在上述描述中编程了多组括号，显然通过计数方式也可以，但是繁琐，我们可以借助栈：
 
class Solution {
public:
    bool isValid(string s) {
        stack stk;
        for(int i=0;i 
1614. 括号的最大嵌套深度（简单难度）
 
给你一个 有效括号字符串 s，返回该字符串的 s 嵌套深度 。
 
输入：s = "(1)+((2))+(((3)))" 输出：3
 
点评
 
最大嵌套深度显然是连续的左括号或者右括号构成的，中间没有右括号来消耗，我们统计栈的大小即可
 
class Solution {
public:
    int maxDepth(string s) {
        int res=0;
        stack stk;
        // 遍历字符串，遇到左括号就入栈，遇到右括号就出栈，统计栈每次的最大深度
        for(char c:s){
            if(c=='(') stk.push(')');
            else if(!stk.empty()&&stk.top()==c) stk.pop();
            int a=stk.size();
            res=max(res,a);
        }
        return res;
    }
};
 
二、括号字符串无效的位置 
 
1249. 移除无效的括号（中等难度）
 
给你一个由 '('、')' 和小写字母组成的字符串 s。
 
你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
 
点评 
 
最少需要移除的括号数量，我们可以借助栈找出所有不匹配的括号位置，其分别是：
 
多余的左括号和多余的右括号，直接全部删除即可
 
class Solution {
public:
    string minRemoveToMakeValid(string s) {
        // 使用栈将所有无法匹配的位置设置为空格
        stack stk;
        for(int i=0;i 
 
32. 最长有效括号（困难难度）
 
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 
点评
 
用栈模拟一遍，标记处所有无法匹配括号的位置，例如 ")()((())"的mark为[1, 0, 0, 1, 0, 0, 0, 0]，此题就变成了寻找最长的连续的0的长度
 
class Solution {
public:
    int longestValidParentheses(string s) {
        // 用栈模拟一遍，标记处所有无法匹配括号的位置
        // 例如 ")()((())"的mark为[1, 0, 0, 1, 0, 0, 0, 0]
        stack stk;
        vector mark(s.length(),0);
        for(int i=0;i 
678. 有效的括号字符串（中等难度）
 
给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。其中*可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
 
点评
 
该题的难点是添加了一个具有通配效果的星号字符，我们可以使用一个专门的栈来放入该字符。
 
需要匹配右括号时，先检查是否有左括号匹配，没有左括号再检查是否有星号匹配；
 
当需要匹配多余的左括号时，先检查是否星栈中是否存在索引大的字符，有则匹配，没有则无法匹配
 
class Solution {
public:
    bool checkValidString(string s) {
        stack left,star;// 左栈存储'(',星栈存储'*'
        // 遍历括号字符串
        for(int i=0;i 
三、回溯生成多个括号字符串 
22. 括号生成（中等难度）
 
剑指 Offer II 085. 生成匹配的括号（中等难度）
 
面试题 08.09. 括号（中等难度）
 
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 
点评：
 
由于有效的括号字符串中左括号数量一定等于右括号数量，所以每个括号组合中一定有n个左括号和n个右括号。
 
 
 
我们可以尝试放入一个左括号或右括号来进行回溯遍历，终止条件是：
 
 
1、从左向右添加括号字符，当右括号数量大于左括号数量时一定不符合
 
 
2、左右括号数量任何一个超过n就一定不符合
 
 
3、左括号数量==右括号数量==n时就一定找到了一个合法的组合
 
 
class Solution {
public:
    vector res;
    string path;
    // 左括号的数量、右括号的数量
    void dfs(int n,int left,int right){
        if(right>left) return;// 从左向右添加括号字符，当右括号多的时候就一定不符合
        if(left>n||right>n) return;// 如果有某个括号超过一半，则一定不是合法的
        // 如果左右括号恰好都为n
        if(left==n&&right==n){
            res.push_back(path);
            return ;
        }
        // 先尝试放入左括号
        path.push_back('(');
        dfs(n,left+1,right);
        path.pop_back();
        // 再尝试放入右括号
        path.push_back(')');
        dfs(n,left,right+1);
        path.pop_back();
    }
    vector generateParenthesis(int n) {
        dfs(n,0,0);
        return res;
    }
};
 
301. 删除无效的括号（困难难度）
 
输入一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。返回所有可能的结果。答案可以按 任意顺序 返回。
 
示例 2：
 
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]
 
点评
 
这道题和1249的区别在于，1249题只需要返回一种最少删除无效括号的情况就行，我们只要能找出一种所有不匹配的括号位置，将其删除即可，这些不匹配的括号位置依赖于我们从左向右搜素的顺序。
 
该题要返回所有最少删除的括号数量的情况，我们借助栈从左向右查找不匹配顺序只能找到其中一种情况；
 
 
 
我们可以使用回溯，先统计字符串中所有的要删除的左右括号数量
 
 
对每个左括号或者右括号字符都尝试删除，然后搜索所有情况，显然终止条件是：
 
 
1、剩余的要删除的括号数量>字符串剩余数量
 
 
2、如果左括号和右括号正好删够，并且是合法字符
 
 
class Solution {
public:
    vector res;
    vector removeInvalidParentheses(string s) {
        int lremove = 0;// 需要删除的左括号数量
        int rremove = 0;// 需要删除的右括号数量
        // 遍历字符串，统计要删除的左括号和右括号的数量
        for (char c : s) {
            if (c == '(') lremove++;
            else if (lremove != 0&&c == ')') lremove--;
            else if (lremove == 0&&c == ')') rremove++;// 要删除的右括号
        }
        dfs(s, 0, lremove, rremove);
        return res;
    }
    void dfs(string& str, int start, int lremove, int rremove) {
        // 如果剩余的字符无法满足去掉的数量要求，直接返回
        if (lremove + rremove > str.size()) return;
        // 如果左括号和右括号正好删够，并且是合法字符串
        if (lremove == 0 && rremove == 0&&isValid(str)) {
            res.push_back(str);
            return;
        }
        // 每个节点从str的[start,:)，尝试分别删除左右括号
        for (int i = start; i < str.size(); i++) {
            // 如果同一层分支相同，则直接跳过
            if (i>start && str[i] == str[i - 1]) continue;
            // 假如要删除
            // 尝试去掉一个左括号
            if ( str[i] == '(') {
                string tmp=str.substr(0, i)+str.substr(i + 1);
                dfs(tmp, i, lremove - 1, rremove);
            }
            // 尝试去掉一个右括号
            if ( str[i] == ')') {
                string tmp=str.substr(0, i)+str.substr(i + 1);
                dfs(tmp, i, lremove, rremove - 1);
            }
        }
    }

    inline bool isValid(const string & s) {
        int cnt = 0;
        // 判断括号字符串是否合法
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                cnt++;
            } else if (s[i] == ')') {
                cnt--;
                if (cnt < 0) {
                    return false;
                }
            }
        }
        return cnt == 0;
    }
};