関小君刷题记

删除无效的括号

删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。

说明: 输入可能包含了除 ( 和 ) 以外的字符。

示例 1:

输入: "()())()"
输出: ["()()()", "(())()"]

示例 2:

输入: "(a)())()"
输出: ["(a)()()", "(a())()"]

示例 3:

输入: ")("
输出: [""]

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=301

解题思路分析：

1. 首先确定字符串中不合理的左括号个数invalidLeft，以及不合理的右括号个数invalidRight。这个方法并不难。我们循环字符串，当遇到左括号时，invalidLeft加一。遇到右括号时，如果invalidLeft大于0，说明当前右括号可以和已有左括号配对，因此消耗一个左括号，即invalidLeft减一。反之如果此时invalidLeft等于0，说明当前出现的右括号之前没有能够配对的左括号，那么，invalidRight加一。重复在此过程，直到循环完所有字符为止。
2. 以字符串首字符为起点进行dfs遍历操作，dfs方法中，需要如下参数：当前字符串，当前index，invalidRight和invalidLeft。显然，当invalidRight与invalidLeft同时为0时，当前字符串很有可能是一个有效结果，不过我们并不能确定，因此这里需要再次检查一下当前字符串是否合法，检查方法与第一步相同。如果当前字符串合理，将其加入返回结果。
3. 接下来是invalidRight或者invalidLeft大于0的情况，我们最终的目的是消除掉所有的不合理字符，因此，我们从当前index向后遍历，如果当前字符是左括号”(“并且invalidLeft大于0，那么当前字符可以被删除，删除后，invalidLeft个数减一，index为当前下标，dfs至下层递归（继续从当前下标之后删除不合理字符）。同理，如果如果当前字符是右括号”)”并且invalidRight大于0，那么当前字符可以被删除，删除后，invalidRight个数减一，index为当前下标，dfs至下层递归。
4. 最后考虑一下去重问题。最简单的方式是使用一个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.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-301-remove-invalid-parentheses-解题思路分析/