题解 | 最长有效的括号字符子序列

import java.util.*;

/**
 * NC255 最长有效的括号字符子序列
 * @author d3y1
 */
public class Solution {
    private ArrayList<String> list = new ArrayList<>();

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串 
     * @return string字符串一维数组
     */
    public String[] maxValidParenthesesStr (String s) {
        return solution(s);
    }

    /**
     * 递归法(dfs): 栈
     * @param s
     * @return
     */
    private String[] solution(String s){
        // 待删除左括号数(多余)
        int delL = 0;
        // 待删除右括号数(多余)
        int delR = 0;

        // 达到最长括号字符子序列时 需要删除的左右括号数
        for(char ch: s.toCharArray()){
            if(ch == '('){
                delL++;
            }else if(ch == ')'){
                if(delL > 0){
                    delL--;
                }else{
                    delR++;
                }
            }
        }

        dfs(s, 0, delL, delR);

        return list.toArray(new String[0]);
    }

    /**
     * 递归
     * @param seq
     * @param start
     * @param delL
     * @param delR
     */
    private void dfs(String seq, int start, int delL, int delR){
        // 最长括号字符子序列
        if(delL==0 && delR==0){
            // 判断是否有效
            if(isValid(seq)){
                list.add(seq);
            }
            return;
        }

        char curCh;
        for(int i=start; i<seq.length(); i++){
            curCh = seq.charAt(i);
            // 重复相同括号
            if(i>start && seq.charAt(i)==seq.charAt(i-1)){
                continue;
            }
            // 剩余不够删除
            if(delL+delR > seq.length()-i){
                return;
            }

            // 删除左括号
            if(delL>0 && curCh=='('){
                dfs(seq.substring(0,i)+seq.substring(i+1), i, delL-1, delR);
            }
            // 删除右括号
            if(delR>0 && curCh==')'){
                dfs(seq.substring(0,i)+seq.substring(i+1), i, delL, delR-1);
            }
        }
    }

    /**
     * 是否有效
     * @param seq
     * @return
     */
    private boolean isValid(String seq){
        Stack<Character> stack = new Stack<>();
        for(char ch: seq.toCharArray()){
            if(ch == '('){
                stack.push(ch);
            }else if(ch == ')'){
                if(stack.isEmpty() || stack.peek()!='('){
                    return false;
                }
                stack.pop();
            }
        }

        return stack.isEmpty();
    }

    /**
     * 是否有效(模拟栈)
     * @param seq
     * @return
     */
    private boolean isOK(String seq){
        int cnt = 0;
        for(char ch: seq.toCharArray()){
            if(ch == '('){
                cnt++;
            }else if(ch == ')'){
                cnt--;
                if(cnt < 0){
                    return false;
                }
            }
        }

        return cnt==0;
    }
}