LeetCode刷题实战301： 删除无效的括号
共 7187字，需浏览 15分钟
·
2021-06-23 20:50
Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid. Return all the possible results. You may return the answer in any order.
示例
示例 1：
输入：s = "()())()"
输出：["(())()","()()()"]
示例 2：
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")("
输出：[""]
解题
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Solution {
private int len;
private char[] charArray;
private Set<String> validExpressions = new HashSet<>();
public List<String> removeInvalidParentheses(String s) {
this.len = s.length();
this.charArray = s.toCharArray();
// 第 1 步：遍历一次，计算多余的左右括号
int leftRemove = 0;
int rightRemove = 0;
for (int i = 0; i < len; i++) {
if (charArray[i] == '(') {
leftRemove++;
} else if (charArray[i] == ')') {
// 遇到右括号的时候，须要根据已经存在的左括号数量决定
if (leftRemove == 0) {
rightRemove++;
}
if (leftRemove > 0) {
// 关键：一个右括号出现可以抵销之前遇到的左括号
leftRemove--;
}
}
}
// 第 2 步：回溯算法，尝试每一种可能的删除操作
StringBuilder path = new StringBuilder();
dfs(0, 0, 0, leftRemove, rightRemove, path);
return new ArrayList<>(this.validExpressions);
}
/**
* @param index 当前遍历到的下标
* @param leftCount 已经遍历到的左括号的个数
* @param rightCount 已经遍历到的右括号的个数
* @param leftRemove 最少应该删除的左括号的个数
* @param rightRemove 最少应该删除的右括号的个数
* @param path 一个可能的结果
*/
private void dfs(int index, int leftCount, int rightCount, int leftRemove, int rightRemove, StringBuilder path) {
if (index == len) {
if (leftRemove == 0 && rightRemove == 0) {
validExpressions.add(path.toString());
}
return;
}
char character = charArray[index];
// 可能的操作 1：删除当前遍历到的字符
if (character == '(' && leftRemove > 0) {
// 由于 leftRemove > 0，并且当前遇到的是左括号，因此可以尝试删除当前遇到的左括号
dfs(index + 1, leftCount, rightCount, leftRemove - 1, rightRemove, path);
}
if (character == ')' && rightRemove > 0) {
// 由于 rightRemove > 0，并且当前遇到的是右括号，因此可以尝试删除当前遇到的右括号
dfs(index + 1, leftCount, rightCount, leftRemove, rightRemove - 1, path);
}
// 可能的操作 2：保留当前遍历到的字符
path.append(character);
if (character != '(' && character != ')') {
// 如果不是括号，继续深度优先遍历
dfs(index + 1, leftCount, rightCount, leftRemove, rightRemove, path);
} else if (character == '(') {
// 考虑左括号
dfs(index + 1, leftCount + 1, rightCount, leftRemove, rightRemove, path);
} else if (rightCount < leftCount) {
// 考虑右括号
dfs(index + 1, leftCount, rightCount + 1, leftRemove, rightRemove, path);
}
path.deleteCharAt(path.length() - 1);
}
}