301. 删除无效的括号

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

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

示例 1:

输入: "()())()"
输出: ["()()()", "(())()"]
示例 2:

输入: "(a)())()"
输出: ["(a)()()", "(a())()"]
示例 3:

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

解题思路1：这道题是参考了grandyang的解法，首先是网友贡献出来的一个暴力解法，因为思路是去除最小数量的无效括号，这个最小数量可以用逐个去除的方法来实现，具体的做法就是，用一个Hashset cur保留当前候选的字符串，初始化为输入字符串s，然后遍历cur，如果当前遍历的元素cs是合法的，那就加入结果res，否则看res是否为空，如果不为空说明和当前元素在同一个cur集的元素里已经有满足条件的元素了，而且比当前元素更先遍历到，也就是和当前元素删除了相同数量括号的这一批候选字符串里，能找到合法的字符串，因此结果肯定在这一批候选字符串中选出，因此我们直接跳过，否则res为空，说明遍历至当前元素还是没有找到合法的字符串，因此我们就要遍历当前字符串，把里面的左括号或者右括号去除一个，然后加入一个新的HashSet next里面，也就是下一批候选字符串，从这个做法中也可以看出，next中的字符串长度始终比cur中的字符串小一，这就是逐个去除括号的结果，我们就是暴力试探。然后当cur中的元素遍历完了之后，我们先检查一下res是否为空，如果为空，说明cur这一批次就没有产生合法的字符串，因此把next赋给cur，然后继续前面讲到的那种循环（因此最外层的循环是while(!cur.isEmpty())），如果res不为空，那我们就直接返回。

代码 t30 s22 java

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();
        HashSet<String> cur = new HashSet<>();
        HashSet<String> next = new HashSet<>();
        cur.add(s);
        while(!cur.isEmpty()){
            next = new HashSet<>();
            for(String cs : cur){
                if(isValid(cs)){
                    res.add(cs);
                }
                if(res.size()!=0) continue;
                for(int i=0; i<cs.length(); i++){
                    if(cs.charAt(i)!=‘(‘ && cs.charAt(i)!=‘)‘) continue;
                    next.add(cs.substring(0, i) + cs.substring(i+1));
                }
            }
            if(res.size()!=0) return res;
            cur = next;
        }
        return res;
    }

    public boolean isValid(String s){
        int cnt = 0;
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i)==‘(‘) cnt++;
            else if(s.charAt(i)==‘)‘ && --cnt<0) return false;
        }
        return cnt==0;
    }
}

解题思路2：
再来看一种递归解法，这种解法首先统计了多余的半括号的数量，用 cnt1 表示多余的左括号，cnt2 表示多余的右括号，因为给定字符串左右括号要么一样多，要么左括号多，要么右括号多，也可能左右括号都多，比如 ")("。所以 cnt1 和 cnt2 要么都为0，要么都大于0，要么一个为0，另一个大于0。好，下面进入递归函数，首先判断，如果当 cnt1 和 cnt2 都为0时，说明此时左右括号个数相等了，调用 isValid 子函数来判断是否正确，正确的话加入结果 res 中并返回即可。否则从 start 开始遍历，这里的变量 start 表示当前递归开始的位置，不需要每次都从头开始，会有大量重复计算。而且对于多个相同的半括号在一起，只删除第一个，比如 "())"，这里有两个右括号，不管删第一个还是删第二个右括号都会得到 "()"，没有区别，所以只用算一次就行了，通过和上一个字符比较，如果不相同，说明是第一个右括号，如果相同则直接跳过。此时来看如果 cnt1 大于0，说明此时左括号多，而如果当前字符正好是左括号的时候，可以删掉当前左括号，继续调用递归，此时 cnt1 的值就应该减1，因为已经删掉了一个左括号。同理，如果 cnt2 大于0，说明此时右括号多，而如果当前字符正好是右括号的时候，可以删掉当前右括号，继续调用递归，此时 cnt2 的值就应该减1，因为已经删掉了一个右括号。这里有一个需要注意的地方，就是当我们要调用递归函数的时候，用的是s.substring(0,i)+s.substring(i+1)，也就是跳过了i这个字符，因此在递归函数里，我们开始遍历的索引start应该还是i，因为i这个字符被取代了，我们还是应该从这个位置开始。

代码 t73 s83 java

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        int cnt1 = 0, cnt2 = 0;
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i)==‘(‘) cnt1++;
            if(cnt1==0 && s.charAt(i)==‘)‘) cnt2++;
            else if(s.charAt(i)==‘)‘) cnt1--;
        }
        List<String> res = new ArrayList<>();
        helper(s, 0, res, cnt1, cnt2);
        return res;
    }

    public void helper(String s, int start, List<String> res, int cnt1, int cnt2){
        if(cnt1==0 && cnt2==0){
            if(isValid(s)){
                // System.out.println(s);
                String t = new String(s);
                res.add(t);
                return;
            }
        }
        for(int i=start; i<s.length(); i++){
            // "()())()"
            if(i!=0 && s.charAt(i)==s.charAt(i-1)) continue;
            if(cnt1>0 && s.charAt(i)==‘(‘){
                helper(s.substring(0, i) + s.substring(i+1), i, res, cnt1-1, cnt2);
            }
            if(cnt2>0 && s.charAt(i)==‘)‘){
                helper(s.substring(0, i) + s.substring(i+1), i, res, cnt1, cnt2-1);
            }
        }
        return;
    }

    public boolean isValid(String s){
        int res = 0;
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i)==‘(‘) res++;
            else if(s.charAt(i)==‘)‘){
                if(res<=0) return false;
                res--;
            }
        }
        return res==0;
    }
}

代码t88 s91 cpp

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        int cnt1 = 0, cnt2 = 0;
        for(char c : s){
            cnt1 += (c==‘(‘);
            if(cnt1==0) cnt2 +=(c==‘)‘);
            else cnt1 -= (c==‘)‘);
        }
        vector<string> res;
        helper(s, 0, cnt1, cnt2, res);
        return res;
    }
private:
    void helper(string s, int start, int cnt1, int cnt2, vector<string>& res){
        if(cnt1==0 && cnt2==0){
            if(isValid(s)){
                res.push_back(s);
                return;
            }
        }
        for(int i=start; i<s.size(); i++){
            if(i!=0 && s[i]==s[i-1]) continue;
            if(cnt1>0 && s[i]==‘(‘){
                helper(s.substr(0, i)+s.substr(i+1), i, cnt1-1, cnt2, res);
            }
            if(cnt2>0 && s[i]==‘)‘){
                helper(s.substr(0, i)+s.substr(i+1), i, cnt1, cnt2-1, res);
            }
        }
        return;
    }

    bool isValid(string s){
        int res = 0;
        for(int i=0; i<s.size(); i++){
            if(s[i]==‘(‘) res++;
            else if(s[i]==‘)‘){
                if(res<=0) return false;
                else res--;
            }
        }
        return res==0;
    }
};

参考资料：
https://www.cnblogs.com/grandyang/p/4944875.html

301. 删除无效的括号

原文：https://www.cnblogs.com/zhengxch/p/14731098.html