提示：如果本文对您有帮助，欢迎点赞支持！
目录
前言
括号系列算法问题是经典的面试高频题，括号系列题目的核心考点就是用栈和DFS 算法。对于括号问题，要明白如下2条规律：
一个「合法」的括号字符串一定满足如下2个条件：
1、括号字符串中的左括号数量一定等于右括号数量**。
2、对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len(p)都有：子串 p[0..i]?中左括号的数量都大于或等于右括号的数量。
?借助栈，我们可以查找一个合法字符串中的所有括号不合法位置，这是我们解决括号问题总结出来的模板：
// 用栈模拟一遍，标记处所有无法匹配括号的位置
// 例如 ")()((())"的mark为[1, 0, 0, 1, 0, 0, 0, 0]
stack<int> stk;
vector<int> mark(s.length(),0);
for(int i=0;i<s.length();++i){
if(s[i]=='(') stk.push(i);
else if(!stk.empty()&&s[i]==')')stk.pop();
else mark[i]=1;// 多余的右括号需要标记
}
// 多余的左括号需要比较
while(!stk.empty()){
mark[stk.top()]=1;
stk.pop();
}?阅读完本文，你将可以提交如下LeetCode题目：
| 类型 | LeetCode题目 |
| 判断一个括号字符串是否有效 | |
| 括号字符串无效的位置 | |
| 回溯生成多个括号字符串 | |
一、判断一个括号字符串是否有效
给定一个包含若干个左右括号的字符串，例如“()))()()()”,判断其是否有效，有效是指：左括号后必须用相同类型的右括号闭合，?左括号必须以正确的顺序闭合。
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，说明左括号全部被匹配，否则剩余左括号
}?给定一个包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
该题在上述描述中编程了多组括号，显然通过计数方式也可以，但是繁琐，我们可以借助栈：
class Solution {
public:
bool isValid(string s) {
stack<char> stk;
for(int i=0;i<s.length();++i) {
// 如果遇到左括号，入栈其对应的右括号
if(s[i]=='(') stk.push(')');
else if(s[i]=='{') stk.push('}');
else if(s[i]=='[') stk.push(']');
// 如果遇到右括号，和栈顶元素对比：相等且栈不空就出栈
else if(!stk.empty()&&s[i]==stk.top())stk.pop();
else return false;
}
return stk.size()==0;
}
};给你一个 有效括号字符串 s，返回该字符串的 s 嵌套深度 。
输入：s = "(1)+((2))+(((3)))" 输出：3
点评
最大嵌套深度显然是连续的左括号或者右括号构成的，中间没有右括号来消耗，我们统计栈的大小即可
class Solution {
public:
int maxDepth(string s) {
int res=0;
stack<char> 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;
}
};二、括号字符串无效的位置
给你一个由 '('、')' 和小写字母组成的字符串 s。
你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
点评?
最少需要移除的括号数量，我们可以借助栈找出所有不匹配的括号位置，其分别是：
多余的左括号和多余的右括号，直接全部删除即可
class Solution {
public:
string minRemoveToMakeValid(string s) {
// 使用栈将所有无法匹配的位置设置为空格
stack<int> stk;
for(int i=0;i<s.length();++i){
if(s[i]=='(') stk.push(i);
else if(!stk.empty()&&s[i]==')') stk.pop();
else if(stk.empty()&&s[i]==')') s[i]=' ';// 多余的右括号
}
while(!stk.empty()){
int i=stk.top();
s[i]=' ';// 多余的左括号
stk.pop();
}
// 遍历字符串，将空格去除
string res;
for(char c:s) {
if(c!=' ') res+=c;
}
return res;
}
};给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
点评
用栈模拟一遍，标记处所有无法匹配括号的位置，例如 ")()((())"的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<int> stk;
vector<int> mark(s.length(),0);
for(int i=0;i<s.length();++i){
if(s[i]=='(') stk.push(i);
else if(!stk.empty()&&s[i]==')')stk.pop();
else mark[i]=1;// 多余的右括号需要标记
}
// 多余的左括号需要比较
while(!stk.empty()){
mark[stk.top()]=1;
stk.pop();
}
// 此题就变成了寻找最长的连续的0的长度
int res=0;
int len=0;
for(int i=0;i<s.length();++i){
if(mark[i]) len=0;
else{
len++;
res=max(res,len);
}
}
return res;
}
};给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。其中*可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
点评
该题的难点是添加了一个具有通配效果的星号字符，我们可以使用一个专门的栈来放入该字符。
需要匹配右括号时，先检查是否有左括号匹配，没有左括号再检查是否有星号匹配；
当需要匹配多余的左括号时，先检查是否星栈中是否存在索引大的字符，有则匹配，没有则无法匹配
class Solution {
public:
bool checkValidString(string s) {
stack<int> left,star;// 左栈存储'(',星栈存储'*'
// 遍历括号字符串
for(int i=0;i<s.length();++i){
// 左括号和星号入栈
if(s[i]=='(') left.push(i);
else if(s[i]=='*') star.push(i);
// 右括号出栈
else if(!left.empty()&&s[i]==')')left.pop();//先尝试出左括号
else if(!star.empty()&&s[i]==')')star.pop();//再尝试出星号
else return false;// 存在多余的右括号无法被匹配
}
// 多余的左括号需要匹配
while(!left.empty()&&!star.empty()){
// 如果左括号索引<星号索引,可以匹配
if(left.top()<star.top()) {
left.pop();
star.pop();
}
else return false;
}
return left.empty();//如果左括号还不为空则false
}
};三、回溯生成多个括号字符串
剑指 Offer II 085. 生成匹配的括号（中等难度）
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
点评：
由于有效的括号字符串中左括号数量一定等于右括号数量，所以每个括号组合中一定有n个左括号和n个右括号。
我们可以尝试放入一个左括号或右括号来进行回溯遍历，终止条件是：
1、从左向右添加括号字符，当右括号数量大于左括号数量时一定不符合
2、左右括号数量任何一个超过n就一定不符合
3、
左括号数量==右括号数量==n时就一定找到了一个合法的组合
class Solution {
public:
vector<string> 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<string> generateParenthesis(int n) {
dfs(n,0,0);
return res;
}
};输入一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。返回所有可能的结果。答案可以按 任意顺序 返回。
示例 2：
输入：s = "(a)())()" 输出：["(a())()","(a)()()"]
点评
这道题和1249的区别在于，1249题只需要返回一种最少删除无效括号的情况就行，我们只要能找出一种所有不匹配的括号位置，将其删除即可，这些不匹配的括号位置依赖于我们从左向右搜素的顺序。
该题要返回所有最少删除的括号数量的情况，我们借助栈从左向右查找不匹配顺序只能找到其中一种情况；
我们可以使用回溯，先统计字符串中所有的要删除的左右括号数量
对每个左括号或者右括号字符都尝试删除，然后搜索所有情况，显然终止条件是：
1、剩余的要删除的括号数量>字符串剩余数量
2、如果左括号和右括号正好删够，并且是合法字符
class Solution {
public:
vector<string> res;
vector<string> 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;
}
};
