20. 有效的括号
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
示例 3：
输入：s = “(]”
输出：false
示例 4：
输入：s = “([)]”
输出：false
示例 5：
输入：s = “{[]}”
输出：true
解析过程：
class Solution {
public boolean isValid(String s) {
//采用栈的思想，如果是左括号，则将其压入栈中等待匹配，如果是右括号，则将其与栈顶元素进行匹配，若匹配成功，则将其出栈，若不成功，或者栈中没有左括号，则字符串无效，返回false
Deque stack=new linkedList<>();
//为了快速判断括号的类型，使用哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。
Map map=new HashMap() {{
put(')','(');
put(']','[');
put('}','{');
}};
int len=s.length();
//若字符串长度为奇数，则返回false
if(len % 2 == 1){
return false;
}
//遍历字符串s
for(int i=0;i
结果：
执行用时：2 ms, 在所有 Java 提交中击败了57.27%的用户
内存消耗：36.4 MB, 在所有 Java 提交中击败了69.32%的用户
通过测试用例：91 / 91
301. 删除无效的括号
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = “()())()”
输出：["(())()","()()()"]
示例 2：
输入：s = “(a)())()”
输出：["(a())()","(a)()()"]
示例 3：
输入：s = “)(”
输出：[""]
解析过程：
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
//给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
//
// 返回所有可能的结果。答案可以按 任意顺序 返回。
// 示例 1：
//输入：s = "()())()"
//输出：["(())()","()()()"]
//
// 示例 2：
//输入：s = "(a)())()"
//输出：["(a())()","(a)()()"]
//
// 示例 3：
//输入：s = ")("
//输出：[""]
//
// 提示：
// 1 <= s.length <= 25
// s 由小写英文字母以及括号 '(' 和 ')' 组成
// s 中至多含 20 个括号
// Related Topics 广度优先搜索 字符串 回溯
//采用回溯方法
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
List arr =new ArrayList<>();
public List removeInvalidParentheses(String s) {
//计算要删除的左右括号数 Lr,Rr
int Lr=0;
int Rr=0;
for(int i=0;i0)
Lr--;
else {
Rr++;
}
}
}
Backtrack(0,Lr,Rr,s);
return arr;
}
//回溯
void Backtrack(int start,int Lr,int Rr,String s){
//完成条件
if(Lr==0 && Rr==0){
if(isValid(s)){
arr.add(s);
}
}
//for s
//离开条件
//做出选择
//回溯
//撤销选择
for (int i = start; i < s.length(); i++) {
//()())( 若当前元素和上一个元素相同，为避免重复，直接跳过
if(i>start && s.charAt(i) == s.charAt(i-1))
continue;
//删除左括号
if(s.charAt(i)=='(' && Lr>0){
//s.substring(0,i)+s.substring(i+1) 删除当前元素之后重新获得的字符串
//substring(begin) 截取从下标begin到str.length()-1内容
// substring（begin，end） 截取指定范围的内容
Backtrack(i,Lr-1,Rr,s.substring(0,i)+s.substring(i+1));
}
//删除右括号
if(s.charAt(i)==')' && Rr>0){
//s.substring(0,i)+s.substring(i+1) 删除当前元素之后重新获得的字符串
Backtrack(i,Lr,Rr-1,s.substring(0,i)+s.substring(i+1));
}
}
}
//判断s是否有效（栈的思想）
boolean isValid(String s){
Stack stack=new Stack<>();
for(int i=0;i
结果：
执行用时：8 ms, 在所有 Java 提交中击败了87.96%的用户
内存消耗：39.1 MB, 在所有 Java 提交中击败了22.74%的用户
通过测试用例：127 / 127
