image.png
删除多余的做括号
思路：
1.首先记录下字符串中多余的左括号和右括号的数量
2.dfs对多余的左右括号进行删除，直到没有多余的左右括号位置，但是这里需要注意，可能会存在重复删除的情况，即‘（））’，因此对于重复的情况，只删除第一个出现的位置
3.当没有多余的左右括号的时候，判断当前字符串是否合法
public List<String> removeInvalidParentheses(String s) {
List<String> list = new ArrayList<>();
int left = 0, right = 0;
for (char ch : s.toCharArray()) {
if (ch == '(') left++;
else if (left != 0 && ch == ')') left--;
else if (left == 0 && ch == ')') right++;
}
dfs(s, 0, left, right, list);
return list;
}
public void dfs(String s, int start, int left, int right, List<String> list) {
if (left == 0 && right == 0) {
if (isValid(s)) list.add(s);
return;
}
for (int i = start; i < s.length(); i++) {
if (i >start && s.charAt(i) == s.charAt(i - 1)) continue;
if (s.charAt(i) == ')' && right > 0) {
dfs(s.substring(0, i) + s.substring(i + 1), i, left, right - 1, list);
}
if (s.charAt(i) == '(' && left > 0) {
dfs(s.substring(0, i) + s.substring(i + 1), i, left - 1, right, list);
}
}
}
public boolean isValid(String s) {
int count = 0;
for (char ch : s.toCharArray()) {
if (ch == '(') count++;
if (ch == ')') count--;
if (count < 0) return false;
}
return count == 0;
}
