leetcode301. 删除无效的括号(java)

leetcode301. 删除无效的括号

难度 困难
https://leetcode.cn/problems/remove-invalid-parentheses/description/

题目描述

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。

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

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

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

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

暴力搜索 + 剪枝

由于题目要求我们将所有（最长）合法方案输出，因此不可能有别的优化，只能进行「递归搜索」。

基本思路：
我们知道所有的合法方案，必然有左括号的数量与右括号数量相等。
首先我们令左括号的得分为 1；右括号的得分为 −1。则会有如下性质：
对于一个合法的方案而言，必然有最终得分为 0；
搜索过程中不会出现得分值为 负数 的情况（当且仅当子串中某个前缀中「右括号的数量」大于「左括号的数量」时，会出现负数，此时不是合法方案）。
同时我们可以预处理出「爆搜」过程的最大得分： max = min(左括号的数量, 右括号的数量)

PS.「爆搜」过程的最大得分必然是：合法左括号先全部出现在左边，之后使用最多的合法右括号进行匹配。

枚举过程中出现字符分三种情况：
左括号：如果增加当前 ( 后，仍为合法子串（即 score+1<=max) 时，我们可以选择添加该左括号，也能选择不添加；
右括号：如果增加当前 ) 后，仍为合法子串（即 score−1>=0) 时，我们可以选择添加该右括号，也能选择不添加；
普通字符：直接添加。

使用 Set 进行方案去重，lenlenlen 记录「爆搜」过程中的最大子串，然后只保留长度等于 lenlenlen 的子串。

代码演示

class Solution {HashSet<String> set = new HashSet<>();String _s;int n,max,len;/*** 删除无效括号* @param s* @return*/public List<String> removeInvalidParentheses(String s) {_s = s;n = s.length();int l = 0, r = 0;int l1 = 0,r1 = 0;for (char c : s.toCharArray()){if (c == '('){l++;l1++;} else if (c == ')') {r1++;if (l != 0){l--;}else {r++;}}}//最大长度len = s.length() - l - r;//左括号和右括号最小数量max = Math.min(l1,r1);dfs(0,"",l,r,0);return new ArrayList<>(set);}/*** 递归* @param index 当前来到的位置* @param cur 选择的字符串* @param l 左边括号 比右边多几个* @param r 右边括号 比左边多几个* @param score 选择的个数*/public void dfs(int index,String cur,int l,int r,int score){//base case 越界条件 直接返回if (l < 0 || r < 0 || score < 0 || score > max){return;}//满足条件 加入到答案中if (l == 0 && r == 0 && cur.length() == len){set.add(cur);}//base case 越界 直接返回if (index == n){return;}char c = _s.charAt(index);if (c == '('){//选择的情况dfs(index + 1,cur + String.valueOf(c),l,r,score + 1);//删除当前括号的情况dfs(index + 1,cur,l - 1,r,score);} else if (c == ')') {//选择的情况dfs(index + 1,cur + String.valueOf(c),l,r,score - 1);//删除当前括号的情况dfs(index + 1,cur,l,r - 1,score);}else {//字符直接加进去dfs(index + 1,cur + String.valueOf(c),l,r,score);}}
}

回溯算法

leetcode212. 单词搜索 II

leetcode1219. 黄金矿工

leetcode306. 累加数