NC255 最长有效的括号字符子序列

import java.util.*;

public class Solution {
    //创建一个List<String>类型的基于数组的表，用ArrayList的无参构造函数
    private List<String> res=new ArrayList<String>();
    public String[] maxValidParenthesesStr (String s) {
        //记录未匹配的左右括号的个数
        int lremove=0;
        int rremove=0;
        int n=s.length();
        //如果是左括号，lremove++
        //如果是右括号:没有左括号，rremove++，否则就匹配掉一个左括号，lremove--
        for(int i=0;i<n;i++){
            if(s.charAt(i)=='('){
                lremove++;
            }else if(s.charAt(i)==')'){
                if(lremove==0){
                    rremove++;
                }else{
                    lremove--;
                }
            }
        }
        //调用helper函数
        helper(s,0,lremove,rremove);
        //创建一个string数组，用toArray()函数将表ans中的元素都复制到这个数组后返回
        String[] ans=new String[res.size()];
        return res.toArray(ans);
    }
    //递归：尝试去掉括号
    private void helper(String s,int start,int lremove,int rremove){
        //递归结束条件，如果都lemove和rremove都等于0，则判断一下是否为合法的括号
        //如果是合法的括号，就加入到答案res中
        if(lremove==0&&rremove==0){
            if(isvalid(s)){
                res.add(s);
            }
            return;
        }
        //从上次的位置开始往后遍历
        for(int i=start;i<s.length();i++){
            //如果发现与前面的括号是一致的，就跳过continue
            if(i!=start&&s.charAt(i)==s.charAt(i-1)){
                continue;
            }
            //如果发现剩下的字符的数量无法满足去掉的数量要求,就结束
            if(lremove+rremove>s.length()-i){
                return;
            }
            //尝试去掉左括号
            //substring(a,b):a:起始位置（包含a）,b(终止位置，不包含b)
            //substring(x):从下标为x的位置一直到字符串的最后一个位置
            if(lremove>0&&s.charAt(i)=='('){
                helper(s.substring(0,i)+s.substring(i+1),i,lremove-1,rremove);
            }
            //尝试去掉右括号
            if(rremove>0&&s.charAt(i)==')'){
                helper(s.substring(0,i)+s.substring(i+1),i,lremove,rremove-1);
            }
        }
    }
    //判断是否是合法的括号序列
    //如果左括号数等于右括号数，则是合法的序列
    private 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--;
           }
           if(cnt<0){
            return false;
           }
       }
       return cnt==0;
    }

}