参考文章：https://labuladong.gitee.io/algo/di-san-zha-24031/jing-dian--a94a0/ru-he-jie--306f6/
题目列表
1. 判断有效性
2. 生成有效的括号
22. 括号生成
921. 使括号有效的最少添加
1541. 平衡括号字符串的最少插入次数
3. 删除得到有效的括号
关键字
判断括号的有效性
生成有效的括号
实现
20. 有效的括号
class Solution {
// 利用栈
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
char[] chars = s.toCharArray();
for(int i=0;i<chars.length;i++){
if(chars[i] == '[' || chars[i] == '{' || chars[i] == '('){
stack.push(chars[i]);
}else{
if(stack.isEmpty()){
return false;
}
if(chars[i] == ']'){
if(stack.peek() == '['){
stack.pop();
}else{
return false;
}
}else if(chars[i] == '}'){
if(stack.peek() == '{'){
stack.pop();
}else{
return false;
}
}else if(chars[i] == ')'){
if(stack.peek() == '('){
stack.pop();
}else{
return false;
}
}
}
}
return stack.isEmpty();
}
}
22. 括号的生成
class Solution {
// 利用left和right两个指针
public List<String> generateParenthesis(int n) {
LinkedList<String> rs = new LinkedList<>();
backtrace(n, n, new StringBuilder(), rs);
return rs;
}
// 回溯所有场景
public void backtrace(int left, int right, StringBuilder cur, LinkedList<String> path){
// 无效的括号，退出
if(left > right){
return;
}
// 走到头了
if(left < 0 || right < 0){
return;
}
// 匹配到括号
if(left == right && left == 0){
path.add(cur.toString());
return;
}
// 先匹配(
cur.append("(");
backtrace(left -1, right, cur, path);
cur.deleteCharAt(cur.length()-1);
// 再匹配)
cur.append(")");
backtrace(left, right-1, cur, path);
cur.deleteCharAt(cur.length()-1);
}
}
301. 删除无效的括号
class Solution {
private List<String> path = new ArrayList<String>();
public List<String> removeInvalidParentheses(String s) {
int lremove = 0;
int rremove = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
lremove++;
} else if (s.charAt(i) == ')') {
if (lremove == 0) {
rremove++;
} else {
lremove--;
}
}
}
backtrace(s, 0, lremove, rremove);
return path;
}
public void backtrace(String s, int idx, int left, int right){
// base
// 左括号和右括号都删除了
if(left == right && left ==0){
// 判断是否是有效的括号
if(isValid(s)){
path.add(s);
}
return;
}
// 注意要for循环，并且从idx开始
for(int i = idx;i<s.length();i++){
// 过滤边相等的情况
if(i!=idx && s.charAt(i-1) == s.charAt(i)){
continue;
}
// 剪枝
// 剩下的字符串已经不够删减了，退出
if(left + right > s.length() - i){
return;
}
// 遇到了左括号，尝试删除i
if(left > 0 && s.charAt(i) == '('){
backtrace(s.substring(0,i) + s.substring(i+1), i, left-1, right);
}
// 遇到了右括号，尝试删除i
if(right > 0 && s.charAt(i) == ')'){
backtrace(s.substring(0,i) + s.substring(i+1), i, left, right-1);
}
}
}
private boolean isValid(String str) {
int cnt = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
cnt++;
} else if (str.charAt(i) == ')') {
cnt--;
if (cnt < 0) {
return false;
}
}
}
return cnt == 0;
}
}
921. 使括号有效的的最少添加
class Solution {
public int minAddToMakeValid(String s) {
int left = 0;
int right = 0;
char[] chars = s.toCharArray();
for(char c:chars){
if(c == '('){
// 有左括号，需要右括号
left++;
}else{
// right可以和left抵消
if(left>0){
left--;
}else{
// 有右括号，需要左括号
right--;
}
}
}
return Math.abs(right) + left;
}
}
1541. 平衡括号字符串的最少插入次数
class Solution {
public int minInsertions(String s) {
// 需要的左括号的数量
int left = 0;
// 需要的右括号的数量
int inserts = 0;
// 为了统计连续的右括号
int index = 0;
int length = s.length();
while(index < length){
char c = s.charAt(index);
if(c == '('){
left++;
index++;
} else {
if(left > 0){
// 有左括号，直接减去
left--;
}else{
// 没有左括号，插入一个左括号
inserts++;
}
if(index < length-1 && s.charAt(index+1) == ')'){
// 下一个是右括号，下一次从下下个开始，因为下一个可以直接消除
index = index + 2;
}else{
// 下一个是左括号，那么需要再插入一个右括号
inserts++;
// index走一位
index++;
}
}
}
if(left>0){
inserts += left*2;
}
return inserts;
}
}
