301 Remove Invalid Parentheses

301. Remove Invalid Parentheses

1. Question

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).
Examples:
"()())()" ->["()()()", "(())()"]
"(a)())()" ->["(a)()()", "(a())()"]
")(" ->[""]

2. Implementation

(1) BFS
class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> res = new ArrayList<>();
Queue<String> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.add(s);
visited.add(s);
boolean minLevel = false;
while (!queue.isEmpty()) {
String curStr = queue.remove();
if (isValid(curStr)) {
minLevel = true;
res.add(curStr);
}
if (minLevel) {
continue;
}
for (int i = 0; i < curStr.length(); i++) {
if (isParenthesis(curStr.charAt(i))) {
String nextStr = curStr.substring(0, i) + curStr.substring(i + 1);
if (!visited.contains(nextStr)) {
queue.add(nextStr);
visited.add(nextStr);
}
}
}
}
return res;
}
public boolean isParenthesis(char c) {
return c == '(' || c == ')';
}
public boolean isValid(String s) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
++count;
}
else if (s.charAt(i) == ')') {
--count;
}
if (count < 0) {
return false;
}
}
return count == 0;
}
}
(2) DFS
class Solution {
public List<String> removeInvalidParentheses(String s) {
int removableLeftParen = 0, removableRightParen = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
++removableLeftParen;
}
else if (c == ')') {
if (removableLeftParen > 0) {
--removableLeftParen;
}
else {
++removableRightParen;
}
}
}
Set<String> res = new HashSet<>();
StringBuilder parens = new StringBuilder();
removeParenthesisByDFS(s, 0, removableLeftParen, removableRightParen, 0, parens, res);
return new ArrayList<>(res);
}
public void removeParenthesisByDFS(String s, int pos, int removableLeftParen, int removableRightParen, int open, StringBuilder parens, Set<String> res) {
if (removableLeftParen < 0 || removableRightParen < 0 || open < 0) {
return;
}
if (pos == s.length()) {
if (removableLeftParen == 0 && removableRightParen == 0 && open == 0) {
res.add(parens.toString());
}
return;
}
char c = s.charAt(pos);
int len = parens.length();
if (c == '(') {
// Remove it
removeParenthesisByDFS(s, pos + 1, removableLeftParen - 1, removableRightParen, open, parens, res);
// Use it
removeParenthesisByDFS(s, pos + 1, removableLeftParen, removableRightParen, open + 1, parens.append(c), res);
}
else if (c == ')') {
// Remove it
removeParenthesisByDFS(s, pos + 1, removableLeftParen, removableRightParen - 1, open, parens, res);
// Use it
removeParenthesisByDFS(s, pos + 1, removableLeftParen, removableRightParen, open - 1, parens.append(c), res);
}
else {
removeParenthesisByDFS(s, pos + 1, removableLeftParen, removableRightParen, open, parens.append(c), res);
}
parens.setLength(len);
}
}

3. Time & Space Complexity

BFS: 时间复杂度: O(n * 2^n), isValid()需要花费O(n), 每个string的character有两种状态(remove/keep), 总共有2^n种状态,所以时间复杂度是O(n * 2^n), 空间复杂度O(2^n)
DFS: 时间复杂度: O(2^n), 空间复杂度O(2^n)