🌕🌕 301. 删除无效的括号

难度: 🌕🌕

问题描述

---

解法 1 - 回溯

class Solution {
    HashSet<String> set = new HashSet<>();
    List<String> res = new ArrayList<>();
    public List<String> removeInvalidParentheses(String s) {
        // 思路：
        // 回溯
        // 首先计算出需要删除的最小数量情况下，左右括号需要的各自删除数量
        // 回溯，判断当前是左括号 | 右括号 | 字符
        // 若是 左 | 右括号，根据 删除 | 保留 进行回溯
        // 剪枝优化
        int lrv = 0;
        int rrv = 0; // 需要删除的右括号数
        int len = s.length();
        for(int i = 0; i < len; i ++) {
            if(s.charAt(i) == '(') {
                lrv ++;
            } else if(s.charAt(i) == ')') {
                // 判断能否和左边的左括号抵消
                if(lrv > 0) {
                    lrv --;
                } else {
                    rrv ++;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        mySol(s, len, len - lrv - rrv, 0, 0, 0, lrv, rrv, sb);
        return res;
    }

    private void mySol(String s, int len, int exp, int index, int lc, int rc, int lrv, int rrv, StringBuilder sb) {
        // 递归终止条件
        if(lrv < 0 || rrv < 0 || lc < rc) {
            return;
        }
        String key = sb.toString() + "#" + index;
        if(set.contains(key)) {
            return; // 去重
        }
        set.add(key);
        if(index == len) {
            // System.out.println(lc + " " + rc + " " + lrv + " " + rrv + " " + sb);
            if(lrv == 0 && rrv == 0 && sb.length() == exp) {
                res.add(sb.toString());
            }
            return;
        }
        // index < len
        char c = s.charAt(index);
        if(c == '(') {
            // 左括号，2 种情况，保留 | 删除
            sb.append('(');
            mySol(s, len, exp, index + 1, lc + 1, rc, lrv, rrv, sb); // 保留
            sb.deleteCharAt(sb.length() - 1);
            mySol(s, len, exp, index + 1, lc, rc, lrv - 1, rrv, sb); // 删除
        } else if(c == ')') {
            sb.append(')');
            mySol(s, len,exp, index + 1, lc, rc + 1, lrv, rrv, sb);
            sb.deleteCharAt(sb.length() - 1);
            mySol(s, len, exp, index + 1, lc, rc, lrv, rrv - 1, sb);
        } else {
            // 其他字符，需要保留
            sb.append(c);
            mySol(s, len, exp, index + 1, lc, rc, lrv, rrv, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

---

输出 1

---

解法

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        // 思路：
        // BFS - 
        // 从当前删除了 n 个括号后，形成的字串集合中，尝试选择里面的一个括号再次删除，加入下一轮的判断队列中，直到某轮有满足条件的结果
        List<String> res = new ArrayList<>();
        HashSet<String> set = new HashSet<>();
        set.add(s);
        while(true) {
            // 遍历 set 当前轮判断是否存在满足条件的字串
            for(String cur: set) {
                if(isValid(cur)) {
                    res.add(cur);
                }
            }
            if(!res.isEmpty()) {
                // 当前轮存在满足条件的结果，当前删除的是最小数量的括号
                return res;
            }
            // res.isEmpty()
            HashSet<String> nextSet = new HashSet<>(); // 暂存下一轮字串
            for(String cur: set) {
                // 遍历 set 所有字串，在每个 cur 中尝试删除其中一个括号
                int len = cur.length();
                for(int i = 0; i < len; i ++) {
                    // 去重
                    if(i > 0 && cur.charAt(i) == cur.charAt(i - 1)) {
                        continue;
                    }
                    if(cur.charAt(i) == '(' || cur.charAt(i) == ')') {
                        nextSet.add(cur.substring(0, i) + cur.substring(i + 1, len));
                    }
                }
            }
            set = nextSet;
        }
    }

    private boolean isValid(String s) {
        int len = s.length();
        int left = 0;
        int right = 0;
        for(int i = 0; i < len; i ++) {
            if(s.charAt(i) == '(') {
                left ++;
            } else if(s.charAt(i) == ')') {
                if(left == 0) {
                    return false;
                } else {
                    left --;
                }
            }
        }
        return left == 0;
    }
}

---

输出