Comment on page
301.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: [""]
Time:
T(n) = n x C(n, n) + (n-1) x C(n, n-1) + ... + 1 x C(n, 1) = n x 2^(n-1)class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> res = new ArrayList<>();
if (s == null) return res;
Set<String> visited = new HashSet();
Queue<String> queue = new LinkedList();
queue.add(s);
visited.add(s);
boolean found = false;
while (!queue.isEmtpy()) {
s = queue.poll();
if (isValid(s)) {
res.add(s);
found = true;
}
if (found) continue; // minimum removal
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) != '(' && s.charAt(i) != ')')
continue;
String t = s.substring(0, i) + s.substring(i + 1);
if (!visited.contains(t)) {
queue.add(t);
visited.add(t);
}
}
}
return res;
}
private boolean isValid(String s) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') count++;
if (c == ')') count--;
if (count < 0) return false;
}
return count == 0;
}
}
Time:
O(2^n) Space: O(n)class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> ans = new ArrayList();
dfs(s, ans, 0, 0, new char[]{'(', ')'});
return ans;
}
private void dfs(String s, List<String> ans, int last_i, last_j, char[] par) {
int stack = 0;
for (int i = last_i; i < s.length; i++) {
if (s.charAt(i) == par[0]) stack++;
if (s.charAt(i) == par[1]) stack--;
if (stack >= 0) {
continue;
} else {
for (int j = last_j; j <= i; j++) {
if (s.charAt(j) == par[1]
&& (j == last_j || s.charAt(j - 1) != par[1])) {
// Recursion: iStart = i since we now have valid # closed parenthesis thru i. jStart = j prevents duplicates
dfs(s.substring(0, j) + s.substring(j + 1), ans, i, j, par);
}
}
return;
}
}
// No invalid closed parenthesis detected. Now check opposite direction, or reverse back to original direction.
String reversed = new StringBuilder(s).reverse().toString();
if (par[0] == '(') {
dfs(reversed, ans, 0, 0, new char[]{')', '('});
} else {
ans.add(reversed);
}
}
}
class Solution {
private Set<String> validExpressions = new HashSet<String>();
private void recurse(
String s,
int index,
int leftCount,
int rightCount,
int leftRem,
int rightRem,
StringBuilder expression) {
// If we reached the end of the string, just check if the resulting expression is
// valid or not and also if we have removed the total number of left and right
// parentheses that we should have removed.
if (index == s.length()) {
if (leftRem == 0 && rightRem == 0) {
this.validExpressions.add(expression.toString());
}
} else {
char character = s.charAt(index);
int length = expression.length();
// The discard case. Note that here we have our pruning condition.
// We don't recurse if the remaining count for that parenthesis is == 0.
if ((character == '(' && leftRem > 0) || (character == ')' && rightRem > 0)) {
this.recurse(
s,
index + 1,
leftCount,
rightCount,
leftRem - (character == '(' ? 1 : 0),
rightRem - (character == ')' ? 1 : 0),
expression);
}
expression.append(character);
// Simply recurse one step further if the current character is not a parenthesis.
if (character != '(' && character != ')') {
this.recurse(s, index + 1, leftCount, rightCount, leftRem, rightRem, expression);
} else if (character == '(') {
// Consider an opening bracket.
this.recurse(s, index + 1, leftCount + 1, rightCount, leftRem, rightRem, expression);
} else if (rightCount < leftCount) {
// Consider a closing bracket.
this.recurse(s, index + 1, leftCount, rightCount + 1, leftRem, rightRem, expression);
}
// Delete for backtracking.
expression.deleteCharAt(length);
}
}
public List<String> removeInvalidParentheses(String s) {
int left = 0, right = 0;
// First, we find out the number of misplaced left and right parentheses.
for (int i = 0; i < s.length(); i++) {
// Simply record the left one.
if (s.charAt(i) == '(') {
left++;
} else if (s.charAt(i) == ')') {
// If we don't have a matching left, then this is a misplaced right, record it.
right = left == 0 ? right + 1 : right;
// Decrement count of left parentheses because we have found a right
// which CAN be a matching one for a left.
left = left > 0 ? left - 1 : left;
}
}
this.recurse(s, 0, 0, 0, left, right, new StringBuilder());
return new ArrayList<String>(this.validExpressions);
}
}
Last modified 2yr ago