LeetCode_回溯_困难_301.删除无效的括号

ゝ一纸荒年。 2023-10-06 22:47 11阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

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

**示例 1：**  
输入：s = “()())()”  
输出：\[“(())()”,“()()()”\]

**示例 2：**  
输入：s = “(a)())()”  
输出：\[“(a())()”,“(a)()()”\]

**示例 3：**  
输入：s = “)(”  
输出：\[“”\]

**提示：**  
1 <= s.length <= 25  
s 由小写英文字母以及括号 ‘(’ 和 ‘)’ 组成  
s 中至多含 20 个括号

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/remove-invalid-parentheses

## 2.思路 ##

（1）回溯  
思路参考[本题官方题解][Link 1]。

相关题目：  
[LeetCode\_栈\_简单\_20.有效的括号][LeetCode_20.]  
[LeetCode\_递归\_回溯算法\_中等\_22.括号生成][LeetCode_22.]  
[LeetCode\_栈\_动态规划\_困难\_32.最长有效括号][LeetCode_32.]  
[LeetCode\_栈\_中等\_856.括号的分数][LeetCode_856.]  
[LeetCode\_栈\_中等\_921.使括号有效的最少添加][LeetCode_921.]

## 3.代码实现（Java） ##

//思路1————回溯
    class Solution {
        
        //存放所有可能的结果
        List<String> res = 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 res;
        }
        
        public void backtrace(String str, int start, int lremove, int rremove) {
        
            if (lremove == 0 && rremove == 0) {
        
                if (isValid(str)) {
        
                    res.add(str);
                }
                return;
            }
            for (int i = start; i < str.length(); i++) {
        
                if (i != start && str.charAt(i) == str.charAt(i - 1)) {
        
                    continue;
                }
                //剪枝操作：如果剩余的字符无法满足去掉的数量要求，直接返回
                if (lremove + rremove > str.length() - i) {
        
                    return;
                }
                //尝试去掉一个左括号
                if (lremove > 0 && str.charAt(i) == '(') {
        
                    backtrace(str.substring(0, i) + str.substring(i + 1), i, lremove - 1, rremove);;
                }
                //尝试去掉一个右括号
                if (rremove > 0 && str.charAt(i) == ')') {
        
                    backtrace(str.substring(0, i) + str.substring(i + 1), i, lremove, rremove - 1);
                }
            }
        }
        
        //判断字符串 str 中的括号是否有效
        public 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;
        }
    }

[Link 1]: https://leetcode.cn/problems/remove-invalid-parentheses/solution/shan-chu-wu-xiao-de-gua-hao-by-leetcode-9w8au/
[LeetCode_20.]: https://blog.csdn.net/weixin_43004044/article/details/118957884
[LeetCode_22.]: https://blog.csdn.net/weixin_43004044/article/details/123493807
[LeetCode_32.]: https://blog.csdn.net/weixin_43004044/article/details/122975965
[LeetCode_856.]: https://blog.csdn.net/weixin_43004044/article/details/127220452
[LeetCode_921.]: https://blog.csdn.net/weixin_43004044/article/details/127160064