校园网站建设和管理工作制度,网站布局设计步骤,写出网站建设的基本流程,建设银行杭州网站首页删除无效的括号 leetcode301. 删除无效的括号题目描述暴力搜索 剪枝代码演示 回溯算法 leetcode301. 删除无效的括号 难度 困难 https://leetcode.cn/problems/remove-invalid-parentheses/description/ 题目描述 给你一个由若干括号和字母组成的字符串 s #xff0c;删除最小… 删除无效的括号 leetcode301. 删除无效的括号题目描述暴力搜索 剪枝代码演示 回溯算法 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.「爆搜」过程的最大得分必然是合法左括号先全部出现在左边之后使用最多的合法右括号进行匹配。 枚举过程中出现字符分三种情况 左括号如果增加当前 ( 后仍为合法子串即 score1max) 时我们可以选择添加该左括号也能选择不添加 右括号如果增加当前 ) 后仍为合法子串即 score−10) 时我们可以选择添加该右括号也能选择不添加 普通字符直接添加。 使用 Set 进行方案去重lenlenlen 记录「爆搜」过程中的最大子串然后只保留长度等于 lenlenlen 的子串。 代码演示
class Solution {HashSetString set new HashSet();String _s;int n,max,len;/*** 删除无效括号* param s* return*/public ListString 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. 累加数
