301. 删除无效的括号

太tm麻烦了,直接看题解

class Solution { private List<String> res = new ArrayList<String>(); public List<String> removeInvalidParentheses(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); return res; } public void helper(String str, int start, int lremove, int rremove) { if (lremove == 0 && rremove == 0) { //数量可以对上,判断是否合法 if (isValid(str)) { res.add(str); } return; } for (int i = start; i < str.length(); i++) { //因为遇到了两个连续相同的字符串,删除哪个都是一样的,所以跳过后一个 //i != start是防止递归重复计算之前的字符 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); } } } public boolean isValid(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; } }