301. 删除无效的括号 (opens new window)

1.搜索+去重

分析：字符串除了括号之外，还存在其它的非括号字符，因此直接观察不好找出无效括号的规律(具体可删除的下标)，所以只能够采用暴力搜索。给出一个复杂案例："(r(()()("

每一个位置如果是括号则可以选择删除或者保留两种操作，这里使用score分数来代替栈的功能判断当前字符是否合法，具体规则如下(本质上是栈的功能)：

• 将“(”加入当前字符串则score加1，“)”则减1。
• 当前分数如果不大于0则不能加入")"
• 当前分数如果超过了整个字符串可匹配的所有括号对数，则不能加入“(”

题目要求删除尽可能少的字符，使用len变量保存结果最大的长度，如果当前得到的字符串长度大于len，则需要清空临时结果集合重新添加。同时存在重复元素，故使用set集合去重保存临时结果。

class Solution {
    int max=0,len=0;
    Set<String> res=new HashSet<>();
    public List<String> removeInvalidParentheses(String s) {
        int neg=0,pos=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='(') pos++;
            if(s.charAt(i)==')') neg++;
        }
        max=Math.min(pos,neg);
        dfs(s,0,0,"");
        return new ArrayList<>(res);
    }
    public void dfs(String s,int index,int score,String path){
        if(index==s.length()){
            if(path.length()>=len&&score==0){
                if(path.length()>len){
                    len=path.length();
                    res.clear();
                }
                res.add(path);
            }
                return;
        }
        if(s.charAt(index)=='('){
            if(score<max){
                dfs(s,index+1,score+1,path+s.substring(index,index+1));
            }
            dfs(s,index+1,score,path);
        }
        else if(s.charAt(index)==')'){
            if(score>0){
                dfs(s,index+1,score-1,path+s.substring(index,index+1));
            }
            dfs(s,index+1,score,path);
        }
        else{
            dfs(s,index+1,score,path+s.substring(index,index+1));
        }
    }
}