【LeetCode】删除无效的括号 [H]（递归）

301. 删除无效的括号 - 力扣（LeetCode）

一、题目

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1：
输入：s = "()())()"
输出：["(())()","()()()"]

示例 2：
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

示例 3：
输入：s = ")("
输出：[""]

提示：

• 1 <= s.length <= 25
• s 由小写英文字母以及括号 '(' 和 ')' 组成
• s 中至多含 20 个括号

二、代码

class Solution {
    public List removeInvalidParentheses(String s) {
        List ans = new ArrayList<>();
        remove(s, 0, 0, ans, new char[] {'(', ')'});
 
        return ans;
    }
 
    
    public void remove(String str, int checkIndex, int deleteIndex, List ans, char[] par) {
        int cnt = 0;
        // 检查每一个位置。找到右括号（左括号）多的情况
        for (int i = checkIndex; i < str.length(); i++) {
            if (str.charAt(i) == par[0]) {
                cnt++;
            } 
            
            if (str.charAt(i) == par[1]) {
                cnt--;
            }
 
            // 一旦出现了cnt小于0的情况，就说明此时与i配对的左括号（右括号）肯定存在多个配对的右括号（左括号），所里我们要开始找可以选择删除的括号
            if (cnt < 0) {
                // 从deleteIndex开始向右边遍历，遍历到i位置，按照我们的规则找到所有可以删除的字符
                for (int j = deleteIndex; j <= i; j++) {
                    // 如果此时是可以删除的字符，就将其删除，并将删除后的字符串继续向下递归
                    if (str.charAt(j) == par[1] && (j == deleteIndex || str.charAt(j - 1) != par[1])) {
                        // 删除玩字符之后的i和j已经指向的是他们原本下一个位置了，所以这里i和j不用加1
                        remove(str.substring(0, j) + str.substring(j + 1, str.length()), i, j, ans, par);
                    }
                }
               // 如果上面循环越界了，说明已经将所有要删除的都删掉了，此时str这个字符。
                // 注意这个返回，当一个字符已经将所有不合法的括号都删掉之后，删掉的同时就是会调用一次递归，就像上面的代码那样，会把删除之后最终的字符串作为参数调用递归
                // 然后新调用的递归的str就是最终已经将所有无效括号都删除的情况，这样在这个递归中就不可能进入到这个if分支，也就不会return，而是直接到最后去收集答案了。
                // 所以还在删除阶段，没有将所有无效括号删除完时，会直接走到这个return返回，不会接着向下执行去收集答案
                return;
            }
 
        }
 
        // 一旦执行到这里，一定是右括号多的情况都已经删除了，或者此时字符串已经是删除之后没有无效括号的字符串了
 
        // 将字符串反转
        String reversed = new StringBuilder(str).reverse().toString();
        // 如果此时par[0] == '('，说明还没有找左括号多的情况，那么我们就将反转的字符串在调用一边递归，并且将new char[] {')', '('}传入，相当于再从反方向找一遍左括号多的情况
        if (par[0] == '(') {
            remove(reversed, 0, 0, ans, new char[] {')', '('});
        // 如果两个方向都已经找完了，那么此时就是答案，将其添加到ans中
        } else {
            ans.add(reversed);
        }
 
    }
}

三、解题思路 

这个题主要是用到递归搜索，详细可以看注释。