LeetCode刷题最好按照标签归类来刷，本文主要对leetcode上的主要括号问题做一个梳理。
括号问题实际上在字符串中常出现，还有一些表达式求值的问题上也有应用，因此本次做一个总结。
- LC20 有效括号
- LC22 括号生成
- LC23 最长有效括号
- LC678. 有效的括号字符串
- LC1190. 反转每对括号间的子串
- LC1249 移除无效的括号
- LC394 字符串解码 (0713补充）
括号问题的核心
括号都是左右括号成对出现的，因此有效的括号必须满足以下条件：
- 在整个字符串中 左右括号的数目必须相同
- 在遍历字符串的过程中，左括号的数目总是要大于等于右括号的数目。
常用的思路：
使用栈结构
对于遍历到左扩号，压入栈中；
对于遍历到右括号，首先判断栈是否为空
1）栈为空，说明当前的右扩号在之前的遍历过程中没有与之匹配的左括号，这个右括号是不成对的。
2）取出栈顶元素，判断是否是左扩号，如果是则说明与当前遍历到的右括号是一对，将元素出栈。
LC20 有效括号
实际上就是利用上述的括号问题的核心内容来解题，只不过这里是有几种不同的括号，需要进行区分。
class Solution {
public boolean isValid(String s) {
if (s == null || s.length() == 0) {
return false;
}
char[] arr = s.toCharArray();
Stack<Character> stack = new Stack<>();
for (int i = 0; i < arr.length; i++) {
char a = arr[i];
if ((a == '(' || a == '[' || a == '{')) {
stack.push(a);
} else {
//当前是右括号，并且栈是空或者栈顶元素与当前符号不匹配
if (a==')' && (stack.isEmpty() || stack.peek() != '(')) {
return false;
}else if (a==']' && (stack.isEmpty() || stack.peek() != '[')) {
return false;
}if (a=='}' && (stack.isEmpty() || stack.peek() != '{')) {
return false;
}else{
//能够匹配，出栈
stack.pop();
}
}
}
return stack.isEmpty();
}
}
LC22 括号生成
给定一个数n,生成一组有效括号（组成n对），这个问题实际上可以用回溯的思想来解决（后面针对回溯也会做一个专题），同时也是对括号核心内容的应用。
实际上就是遍历整个搜索树，选取满足要求的路径。
我们可以使用递归的方式来求解，其中需要知道的状态是：
- 当前生成的是第几个字符
- 当前产生的左括号有多少个
然后递归遍历整个搜索树，实际上就是前序遍历二叉树，只不过我们要记录路径而已。为了减少不必要的递归，我们可以进行剪枝，即写出递归的终止条件
1）当左括号的数目超过n时，此时可以直接退出
2）当左括号的数目小于右括号，此时不可能是有效，直接退出
3）当前是最后的字符，且满足左右括号数目相同，添加路径
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
dfs(2 * n, 0, 0, new StringBuilder(), res);
return res;
}
void dfs(int len, int index, int left, StringBuilder sb, List<String> res) {
int cur_right = index - left;
if (left < cur_right || left > len / 2) {
return;
}
if (index == len) {
if (left == cur_right) {
res.add(sb.toString());
}
return;
}
sb.append("(");
left++;
f(len, index + 1, left, sb, res);
sb.delete(sb.length() - 1, sb.length());
left--;
sb.append(')');
f(len, index + 1, left, sb, res);
sb.delete(sb.length() - 1, sb.length());
left--;
}
}
LC23 最长有效括号
一般求解最值问题我们可以考虑动态规划。
动态规划其实很类似数学归纳法，我们从整体着手，思考问题，推出状态方程，写代码的时候则是从基数开始进行初始化，然后利用状态方程进行迭代。
我们假设 dp[i]表示以i下标位置字符为结尾向左边扩充能够找到的连续的有效括号的长度。思考一下,这样定义之后如果求解状态方程。
dp[i] 与dpj
如果i位置是’(’，那么dp[i]=0;
如果i位置是’)’，那么我们需要考虑它的前一个位置i-1的字符，
1）如果s[i-1]=’(’，那么说明[i-1,i]就是一个有效的括号，那么这个是最长的有效括号么，也就是说dp[i]是否就止于此。显然不是，我们还需要考虑i-2位置前是否有有效括号，这里就能看出来和我们的定义相吻合了，不就是dp[i-2]么，因此dp[i]=dp[i-2]+2
2）如果s[i-1]=’)’，如s=’)(())’ 那么我们得找到与当前这个’)‘相匹配最远左括号位置，实际上就是 i-dp[i-1]-1处 ，记 pre = i-dp[i-1]-1
如果s[pre]=’(‘那么dp[i]=dp[i-1]+2+(pre>=1?dp[pre-1]:0)
实际上这1）2）两者可以合并起来，因为1）中相当于dp[i-1]=0 pre=i-1
class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int[] f = new int[s.length()];
int res = 0;
int pre = 0;
for (int i = 1; i < s.length(); i++) {
char tmp = s.charAt(i);
if (tmp == ')') {
pre = i - f[i - 1] - 1;
// 对应两种情况 () || )(()())
//pre指向的当前的）应该要匹配的位置
if(pre>=0 && s.charAt(pre)=='(' ){
f[i] = f[i - 1] + 2 + (pre >= 1 ? f[pre - 1] : 0);
}
}
res = Math.max(res,f[i]);
}
return res;
}
}
LC678. 有效的括号字符串
字符串中有号，可以替代左括号或者右括号。
使用栈结构来进行操作，使用两个栈分别存储左括号的下标和星号的下标
遍历字符串，如果碰到左括号就将对应字符下标压入栈中
如果是号，对应下标也压入栈中，
如果是右括号，那么此时需要考虑
如果栈1不为空，那么将其出栈，与当前右括号进行匹配
否则如果栈2不为空 那么将其出栈，用作左括号与当前右括号匹配
如果都为空，返回false,说明当前右括号没有相应的左括号或者星号预期匹配
此时判断栈1和栈2的大小，栈1中存储的都是右括号，栈2中存储的都是星号
如果栈1的大小大于栈2，那么一定不能匹配
否则，需要比较栈1栈顶的元素大小是否小于栈2栈顶的元素大小，这样*号才能与左括号匹配上，否则这个栈顶的左括号必然不能匹配。
class Solution {
public boolean checkValidString(String s) {
if (s == null || s.length() == 0) {
return false;
}
// stack store left
Stack<Integer> stack1 = new Stack<>();
// stack store star
Stack<Integer> stack2 = new Stack<>();
char[] arr = s.toCharArray();
for (int i = 0; i < arr.length; i++) {
char c = arr[i];
if (c == '(') {
stack1.push(i);
} else if (c == ')') {
// before this has no left and star
if (!stack1.isEmpty()) {
stack1.pop();
} else if (!stack2.isEmpty()) {
//has star, use star as left to match
stack2.pop();
} else {
return false;
}
} else {
stack2.push(i);
}
}
// has no enough star to match left
if (stack2.size() < stack1.size()) {
return false;
}
// star use as right star index must be larger than left
while (!stack1.isEmpty() && !stack2.isEmpty()) {
if (stack1.peek() > stack2.peek()) {
return false;
}
stack1.pop();
stack2.pop();
}
return true;
}
}
LC1190. 反转每对括号间的子串
要反转括号内的数据，而且是从内到外，而我们遍历的顺序是从外到内，因此可以使用栈结构。
用一个变量str记录上一次遍历到左括号到本次遍历到左括号的之间的字符串。
1）本次遍历到左括号时，将str压入栈中，然后将str设置为空字符串，重新记录本次左括号到下次左括号之间的字符；
2）本次遍历到字符时，将字符添加到str后；
3）本次遍历到右括号时，说明需要进行结算，把本次括号之间的字符进行反转，即将str反转，同时将栈中的栈顶元素与该反转后的字符串进行拼接，赋值给str
class Solution {
public String reverseParentheses(String s) {
if (s == null || s.length() == 0) {
return "";
}
char[] arr = s.toCharArray();
Stack<String> stack = new Stack<>();
String str = "";
for (int i = 0; i < arr.length; i++) {
char c = arr[i];
if (c == '(') {
// push stack
stack.push(str);
str = "";
} else if (c == ')') {
// pop data and reverse
// 反转当前括号的数，并与前一个括号的数进行合并
String tmp = reverse(str);
str = stack.peek() + tmp;
stack.pop();
} else {
str += c;
}
}
return str;
}
public String reverse(String s) {
char[] arr = s.toCharArray();
int i = 0, j = arr.length - 1;
while (i < j) {
char tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
return String.valueOf(arr);
}
}
LC1249 移除无效的括号
实际上就是对于括号问题核心内容的直接应用，只不过我们需要记录没有成对的单独括号的位置，在遍历的时候剔除就可。具体参见代码：
class Solution {
public String minRemoveToMakeValid(String s) {
if (s == null || s.length() == 0) {
return "";
}
//存储下标
Stack<Integer> stack = new Stack<>();
//存储未能够匹配的下标
Set<Integer> notMatchSet = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
Character c = s.charAt(i);
if(c == '('){
stack.push(i);
}else if (c == ')'){
if(stack.isEmpty()){
notMatchSet.add(i);
}else {
stack.pop();
}
}
}
//如果此时栈中还有元素 说明有新增的元素未匹配上 也要加入到集合 如 ”))((“
while (!stack.isEmpty()){
notMatchSet.add(stack.pop());
}
StringBuilder sb = new StringBuilder();
for(int i=0;i<s.length();i++){
if(!notMatchSet.contains(i)){
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}
LC394 字符串解码
本题和LC1190十分类似，只不过我们需要使用两个栈，一个数字栈用来存储字符串重复的次数，一个字符串栈，用来两个存储遍历过程中两个左括号”[“之间的字符串。
当遇到右括号时，进行结算。具体代码及详细解释如下：
class Solution {
private boolean isLetter(char c) {
if (c >= 'a' && c <= 'z') {
return true;
}
if (c >= 'A' && c <= 'Z') {
return true;
}
return false;
}
/**
* 数字: 判断下一个是否是数字，得到重复次数
* 左括号 [：入符号栈
* 右括号 ]：进行结算
* 字母：用一个变量先存起来，遇到左括号就入栈
*
* @param s
* @return
*/
public String decodeString(String s) {
if (s == null || s.length() == 0) {
return "";
}
char[] arr = s.toCharArray();
Stack<Integer> numStack = new Stack<>();
Stack<String> opsStack = new Stack<>();
int len = arr.length;
//用来记录两个左括号之间的字符串
//遇到左括号，将其压栈后，重置为空，继续记录到下一个左括号的值
//遇到右括号，说明该字符串为与当前右括号相匹配的左括号之间的字符串值
String tmp = "";
for (int i = 0; i < len; i++) {
char c = arr[i];
//当前是数字
if (Character.isDigit(c)) {
int j = i;
int num = 0;
while (j < len && Character.isDigit(arr[j])) {
num = 10 * num + arr[j++] - '0';
}
numStack.push(num);
i = j - 1;
} else if (isLetter(c)) {
tmp += String.valueOf(c);
} else if (c == '[') {
// [前的字符串压入栈中
opsStack.push(tmp);
// 清空字符串
tmp = "";
} else {
//遇到了右括号，要开始进行结算 此时从数字栈中弹出数据 表示该字符的次数
StringBuilder sb = new StringBuilder();
if (!numStack.isEmpty()) {
// 当前字符串 tmp 的重复次数
int cnt = numStack.pop();
for (int j = 0; j < cnt; j++) {
sb.append(tmp);
}
}
// 栈顶元素 拼接当前 ] 内的字符串
tmp = opsStack.peek() + sb.toString();
opsStack.pop();
}
}
return tmp;
}
}