参考文章：https://labuladong.gitee.io/algo/di-san-zha-24031/jing-dian--a94a0/ru-he-jie--306f6/

题目列表

1. 判断有效性

20. 有效的括号
32. 最长有效括号

2. 生成有效的括号

22. 括号生成
921. 使括号有效的最少添加
1541. 平衡括号字符串的最少插入次数

3. 删除得到有效的括号

301.删除无效的括号

关键字

判断括号的有效性
生成有效的括号

实现

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;
    }
}