301. Remove Invalid Parentheses (Hard)
https://leetcode.com/problems/remove-invalid-parentheses/
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Note: The input string may contain letters other than the parentheses (
and )
.
Example 1:
Input: "()())()" Output: ["()()()", "(())()"]
Example 2:
Input: "(a)())()" Output: ["(a)()()", "(a())()"]
Example 3:
Input: ")(" Output: [""]
Solutions
class Solution {
// This is a brute force solution.
// the minimum delete operations. Any outcome patterns the requires more than this is invalid.
int minDelete = Integer.MAX_VALUE;
public List<String> removeInvalidParentheses(String s) {
List<String> ans = new ArrayList<>();
if (s == null || s.length() == 0) {
ans.add("");
return ans;
}
minDelete = calculateMinDelete2(s);
System.out.println(minDelete);
recurse(s.toCharArray(), 0, "", ans, 0, 0, 0);
if (ans.size() == 0) {
ans.add("");
}
return ans;
}
private int calculateMinDelete(String s) {
int invalidP = 0;
int openP = 0;
int closeP = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
openP++;
}
if (s.charAt(i) == ')') {
closeP++;
}
if (openP < closeP) {
openP = 0;
closeP = 0;
invalidP++;
}
}
// do not forget the situation the the last char is open parenthese, say "(()("
if (openP > closeP) {
// be careful, not invalidP++;
invalidP += openP - closeP;
}
return invalidP;
}
private int calculateMinDelete2(String s) {
int invalidClose = 0;
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.add('(');
continue;
}
if (s.charAt(i) == ')') {
if (stack.isEmpty()) {
invalidClose++;
} else {
stack.pop();
}
}
}
return invalidClose + stack.size();
}
private void recurse(char[] str, int start, String result, List<String> ans, int openP, int closeP, int delete) {
if (delete > minDelete) {
return;
}
// reach the end of the string
if (start == str.length) {
// invalid parentheses
if (openP != closeP) {
return;
}
// already covered pattern
if (ans.contains(result)) {
return;
}
ans.add(result);
return;
}
// Open parentheses can never be less than close parentheses. Otherwise it is invalid parentheses string.
if (openP < closeP) {
return;
}
if (str[start] == '(') {
recurse(str, start + 1, result + "(", ans, openP + 1, closeP, delete);
recurse(str, start + 1, result, ans, openP, closeP, delete + 1);
return;
}
if (str[start] == ')') {
recurse(str, start + 1, result + ")", ans, openP, closeP + 1, delete);
recurse(str, start + 1, result, ans, openP, closeP, delete + 1);
return;
}
recurse(str, start + 1, result + str[start], ans, openP, closeP, delete);
}
}