?LeetCode刷題實戰(zhàn)301： 刪除無效的括號
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] == ')') {
// 遇到右括號的時候，須要根據(jù)已經(jīng)存在的左括號數(shù)量決定
if (leftRemove == 0) {
rightRemove++;
}
if (leftRemove > 0) {
// 關(guān)鍵：一個右括號出現(xiàn)可以抵銷之前遇到的左括號
leftRemove--;
}
}
}
// 第 2 步：回溯算法，嘗試每一種可能的刪除操作
StringBuilder path = new StringBuilder();
dfs(0, 0, 0, leftRemove, rightRemove, path);
return new ArrayList<>(this.validExpressions);
}
/**
* @param index 當前遍歷到的下標
* @param leftCount 已經(jīng)遍歷到的左括號的個數(shù)
* @param rightCount 已經(jīng)遍歷到的右括號的個數(shù)
* @param leftRemove 最少應(yīng)該刪除的左括號的個數(shù)
* @param rightRemove 最少應(yīng)該刪除的右括號的個數(shù)
* @param path 一個可能的結(jié)果
*/
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 != ')') {
// 如果不是括號，繼續(xù)深度優(yōu)先遍歷
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);
}
}