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

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