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

import java.util.*;

// 回溯枚举所有子序列，注意括号匹配，取最长子序列去重
// 字母不影响括号匹配，都取

public class Solution {
    public String[] maxValidParenthesesStr (String s) {
        dfs(s.toCharArray(), 0, 0, 0, 0);
        return res.toArray(new String[0]);
    }

    char[] path = new char[26];
    Set<String> res = new HashSet<>();
    int maxLen = 0;

    void dfs(char[] s, int i, int left, int right, int len) {
        if (i == s.length) {
            if (left == right) {
                if (len + 1 >= maxLen) {
                    if (len + 1 > maxLen) res.clear();
                    res.add(String.valueOf(path, 0, len));
                    maxLen = len + 1;
                }
            }
            return;
        }

        if (s[i] == '(') { // 左括号都可以取
            if (s.length - i - 1 + right >= left) {
                path[len] = s[i];
                dfs(s, i + 1, left + 1, right, len + 1); // 选
            }
            dfs(s, i + 1, left, right, len); // 不选
        } else if (s[i] == ')') {
            if (left >= 1 + right) { // 右括号不能多余左括号
                path[len] = s[i];
                dfs(s, i + 1, left, right + 1, len + 1);
            }
            dfs(s, i + 1, left, right, len);
        } else {
            path[len] = s[i];
            dfs(s, i + 1, left, right, len + 1);
        }
    }
}

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;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串一维数组
     */
   private List<String> res3 = new ArrayList<String>();

	public String[] maxValidParenthesesStr(String s) {
		int lremove = 0;
		int rremove = 0;
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == '(') {
				lremove++;
			} else if (s.charAt(i) == ')') {
				if (lremove == 0) {
					rremove++;
				} else {
					lremove--;
				}
			}
		}
		helper(s, 0, lremove, rremove);
		String[] strings = new String[res3.size()];
		return res3.toArray(strings);
	}

	private void helper(String str, int start, int lremove, int rremove) {
		if (lremove == 0 && rremove == 0) {
			if (isValid2(str)) {
				res3.add(str);
			}
			return;
		}

		for (int i = start; i < str.length(); i++) {
			if (i != start && str.charAt(i) == str.charAt(i - 1)) {
				continue;
			}
			// 如果剩余的字符无法满足去掉的数量要求，直接返回
			if (lremove + rremove > str.length() - i) {
				return;
			}
			// 尝试去掉一个左括号
			if (lremove > 0 && str.charAt(i) == '(') {
				helper(str.substring(0, i) + str.substring(i + 1), i, lremove - 1, rremove);
			}
			// 尝试去掉一个右括号
			if (rremove > 0 && str.charAt(i) == ')') {
				helper(str.substring(0, i) + str.substring(i + 1), i, lremove, rremove - 1);
			}
		}
	}

	//判断是否为有效的括号对
	private boolean isValid2(String str) {
		int cnt = 0;
		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) == '(') {
				cnt++;
			} else if (str.charAt(i) == ')') {
				cnt--;
				if (cnt < 0) {
					return false;
				}
			}
		}
		return cnt == 0;
	}
}