删除无效的括号
删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。
说明: 输入可能包含了除 ( 和 ) 以外的字符。
示例 1:
输入: "()())()" 输出: ["()()()", "(())()"]
示例 2:
输入: "(a)())()" 输出: ["(a)()()", "(a())()"]
示例 3:
输入: ")("
输出: [""]如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=301
解题思路分析：
- 首先确定字符串中不合理的左括号个数invalidLeft，以及不合理的右括号个数invalidRight。这个方法并不难。我们循环字符串，当遇到左括号时，invalidLeft加一。遇到右括号时，如果invalidLeft大于0，说明当前右括号可以和已有左括号配对，因此消耗一个左括号，即invalidLeft减一。反之如果此时invalidLeft等于0，说明当前出现的右括号之前没有能够配对的左括号，那么，invalidRight加一。重复在此过程，直到循环完所有字符为止。
- 以字符串首字符为起点进行dfs遍历操作，dfs方法中，需要如下参数：当前字符串，当前index，invalidRight和invalidLeft。显然，当invalidRight与invalidLeft同时为0时，当前字符串很有可能是一个有效结果，不过我们并不能确定，因此这里需要再次检查一下当前字符串是否合法，检查方法与第一步相同。如果当前字符串合理，将其加入返回结果。
- 接下来是invalidRight或者invalidLeft大于0的情况，我们最终的目的是消除掉所有的不合理字符，因此，我们从当前index向后遍历，如果当前字符是左括号”(“并且invalidLeft大于0，那么当前字符可以被删除，删除后，invalidLeft个数减一，index为当前下标，dfs至下层递归（继续从当前下标之后删除不合理字符）。同理，如果如果当前字符是右括号”)”并且invalidRight大于0，那么当前字符可以被删除，删除后，invalidRight个数减一，index为当前下标，dfs至下层递归。
- 最后考虑一下去重问题。最简单的方式是使用一个HashSet，然而这样做效率并不高。其实在第3步，我们有去重的方法。循环中，如果当前字符与前一字符相同的话，那么当前字符无论如何操作，实际上与前一字符的dfs逻辑没有任何区别，因此，当遇到连续的重复字符时，直接跳过即可。
总结：本题的核心思想是dfs深度优先搜索，我们可以将字符串中每个字符都看作是节点，每个节点的下一个节点集合是剩下的所有不合理节点。即当invalidLeft大于0时，当前下标之后的所有左括号都是不合理节点，同理，当invalidRight大于0时，当前下标之后的所有右括号也都是不合理节点。路径上选择的不同，也导致了多种返回结果的出现。
实现代码：
List<String> res=new ArrayList<>(); // 返回结果
public List<String> removeInvalidParentheses(String s) {
int invalidLeft=0; // 不合理左括号个数
int invalidRight=0; // 不合理右括号个数
char[] arr=s.toCharArray();
for(char c:arr){
if(c=='(') invalidLeft++;
if(c==')'){
if(invalidLeft>0)invalidLeft--;
else invalidRight++;
}
} // TODO 这部分代码可以与isValid方法合并
dfs(s,invalidLeft,invalidRight,0); // dfs每一种删除方式
return res;
}
void dfs(String s, int invalidLeft, int invalidRight, int index){
if(invalidLeft==0&&invalidRight==0){ // 如果不合理括号已删除完
if(isValid(s)) { // 查看当前字符串是否合理
res.add(s); // 如果合理，加入返回结果
}
return;
}
if(index==s.length()){ // 如果下标越界，返回
return;
}
for(int i=index;i<s.length();i++){ // 从当前下标向后循环
char c = s.charAt(i); // 当前字符
// 排重，如果当前字符与前一字符相同，跳过
if(i>index&&c==s.charAt(i-1)) continue;
// 如果当前字符是左括号，并且invalidLeft大于0
if(c=='('&&invalidLeft>0){
StringBuilder sb=new StringBuilder(s);
sb.deleteCharAt(i); // 删除当前字符
dfs(sb.toString(),invalidLeft-1,invalidRight,i); // dfs至下一节点
}
// 如果当前字符是右括号，并且invalidRight大于0
if(c==')'&&invalidRight>0){
StringBuilder sb=new StringBuilder(s);
sb.deleteCharAt(i); // 删除当前字符
dfs(sb.toString(),invalidLeft,invalidRight-1,i); // dfs至下一节点
}
}
}
// 判断字符串s是否合理
boolean isValid(String s){
int invalidLeft=0;
int invalidRight=0;
char[] arr=s.toCharArray();
for(char c:arr){
if(c=='(') invalidLeft++;
if(c==')'){
if(invalidLeft>0)invalidLeft--;
else invalidRight++;
}
}
return invalidLeft==0&&invalidRight==0;
}本题解法执行时间为3ms。
Runtime: 3 ms, faster than 77.81% of Java online submissions for Remove Invalid Parentheses.
Memory Usage: 39.6 MB, less than 71.60% of Java online submissions for Remove Invalid Parentheses.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-301-remove-invalid-parentheses-解题思路分析/