BiruLyu
5/29/2017 - 10:59 PM

## https://www.hrwhisper.me/leetcode-remove-invalid-parentheses/ http://blog.csdn.net/qq508618087/article/details/50408894

``````public class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> ans = new ArrayList<>();
remove(s, ans, 0, 0, new char[]{'(', ')'});
return ans;
}

public void remove(String s, List<String> ans, int last_i, int last_j,  char[] par) {
for (int stack = 0, 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;
for (int j = last_j; j <= i; ++j)
if (s.charAt(j) == par[1] && (j == last_j || s.charAt(j - 1) != par[1]))
remove(s.substring(0, j) + s.substring(j + 1, s.length()), ans, i, j, par);
return;
}
String reversed = new StringBuilder(s).reverse().toString();
if (par[0] == '(') // finished left to right
remove(reversed, ans, 0, 0, new char[]{')', '('});
else // finished right to left
ans.add(reversed);
}
}``````
``````sample 2 ms submission
public class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> ans = new ArrayList<>();
removeLeft(s, ans, new char[s.length()], 0, 0, 0);
return ans;
}

private static void removeLeft(String s, List<String> ans, char[] buf, int pos, int start, int last) {
int p = start, b = 0;
for (int i = start; i < s.length(); ++i) {
if (s.charAt(i) == '(') {
++b;
} else if (s.charAt(i) == ')') {
--b;
}
if (b <= 0) {
p = i + 1;
}
if (b < 0) {
for (int j = last; j <= i; ++j) {
if (s.charAt(j) == ')' && (j == last || s.charAt(j - 1) != ')')) {
s.getChars(last, j, buf, pos);
removeLeft(s, ans, buf, pos + j - last, i + 1, j + 1);
}
}
return;
}
}
s.getChars(last, p, buf, pos);
int rem = b + (last - pos); // total number of parentheses to remove, including already removed
removeRight(s, ans, buf, buf.length - rem, buf.length - rem, s.length() - 1, s.length() - 1, p);
}

private static void removeRight(String s, List<String> ans, char[] buf, int pos, int len,
int start, int last, int p) {
int b = 0;
for (int i = start; i >= p; --i) {
if (s.charAt(i) == ')') {
++b;
} else if (s.charAt(i) == '(') {
--b;
}
if (b < 0) {
for (int j = last; j >= i; --j) {
if (s.charAt(j) == '(' && (j == last || s.charAt(j + 1) != '(')) {
s.getChars(j + 1, last + 1, buf, pos - (last - j));
removeRight(s, ans, buf, pos - (last - j), len, i - 1, j - 1, p);
}
}
return;
}
}
s.getChars(p, last + 1, buf, pos - (last + 1 - p));
ans.add(new String(buf, 0, len));
}
}``````
``````public class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> res = new ArrayList<String>();
//if(s == null || s.length() == 0) return res; "" ==> [""]
if(s == null) return res;
Queue<String> frontier = new LinkedList<String>();
Set<String> explored = new HashSet<String>();

frontier.offer(s);
boolean flag = false; // stop exploring to next level after finding res in the current level
while(!frontier.isEmpty()){
String cur = frontier.poll();
if(isValid(cur)) {
res.add(cur);
flag = true;
}
if(flag) {
continue;
}
StringBuilder sb = new StringBuilder();
sb.append(cur);
for(int i = 0; i < cur.length(); i++){
char temp = sb.charAt(i);
if(temp == '(' || temp == ')') {
sb.deleteCharAt(i);
String nextStr = sb.toString();
if(!explored.contains(nextStr)) {
frontier.offer(nextStr);
explored.add(nextStr);
}
sb.insert(i, temp);
}

}
}
return res;
}

public boolean isValid(String str){
int count = 0;
for( int i = 0; i < str.length(); i++) {
char temp = str.charAt(i);
if (temp == '(') {
count++;
} else if (temp == ')') {
if(count == 0) {
return false;
}
count--;
}
}
return count == 0;
}
}

/*
"()())()"
"(a)())()"
")("
""
*/``````