301. Remove Invalid Parentheses (Hard) 考简化版
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())()"]
")(" -> [""]
Solution 1: DFS O(n * n^2); O(n)
/**
* DFS O(n*k), k: # of recursion calls
* 1.use a counter to check if a string of parentheses is valid
* 2.restrict to remove the first ) in a series of consecutive )s to avoid duplicate results
* 3.After the removal, the prefix is then valid.
* We then call the function recursively to solve the rest of string
* 4.keep tracking the last removal position and only remove ‘)’ after that.
* 5.reverse the string and reuse the code
*/
public List<String> removeInvalidParentheses(String s) {
List<String> res = new ArrayList<>();
if (s == null) {
return res;
}
dfs(res, s, 0, 0, new char[]{'(', ')'});
return res;
}
private void dfs(List<String> res, String s, int iStart, int jStart, char[] par) {
int count = 0; //use a counter to simulate the stack
for (int i = iStart; i < s.length(); i++) {
if (s.charAt(i) == par[0]) {
count++;
}
if (s.charAt(i) == par[1]) {
count--;
}
if (count >= 0) {
continue;
}
for (int j = jStart; j <= i; j++) {
if (s.charAt(j) == par[1] && (j == jStart || s.charAt(j) != s.charAt(j - 1))) {
dfs(res, s.substring(0, j) + s.substring(j + 1), i, j, par);
}
}
return;
}
String reversed = new StringBuilder(s).reverse().toString();
if (par[0] == '(') {
dfs(res, reversed, 0, 0, new char[]{')', '('}); // important: 0, 0
} else {
res.add(reversed);
}
}
Solution 2: BFS O(n * n^2); O(n)
https://leetcode.com/problems/remove-invalid-parentheses/discuss/75032/Share-my-Java-BFS-solution
/**
* BFS.
* Generate all possible next strings by removing one paren from current string.
* First add the original string to a queue and a set to start BFS.
* While queue is not empty:
* | Poll a string from the queue.
* | Check if the polled string is valid, if its valid:
* | Set the found flag. We don't need to generate next level.
* | If found is true:
* | Continue to the next string in queue.
* | If found is false:
* | Generate all possible strings for the next level by removing one parentheses.
* <p>
* Note that once we found one valid string, we know the minimum number.
* No need to generate the next possible strings anymore.
* Use a String set to avoid BFS cycles or duplicate checks.
*/
public List<String> removeInvalidParentheses(String s) {
List<String> res = new ArrayList<>();
// sanity check
if (s == null) return res;
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
// initialize
queue.add(s);
visited.add(s);
boolean found = false;
while (!queue.isEmpty()) {
s = queue.poll();
if (isValid(s)) {
// found an answer, add to the result
res.add(s);
found = true;
}
if (found) continue;
// generate all possible states
for (int i = 0; i < s.length(); i++) {
// we only try to remove left or right paren
if (s.charAt(i) != '(' && s.charAt(i) != ')') continue;
String t = s.substring(0, i) + s.substring(i + 1);
if (!visited.contains(t)) {
// for each state, if it's not visited, add it to the queue
queue.add(t);
visited.add(t);
}
}
}
return res;
}
// helper function checks if string s contains valid parantheses
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-- == 0) return false;
}
return count == 0;
}
Follow Up:
1.简化版，只输出一个有效结果，15年3月就有此题，follow up: 用stack实现。超级高频
按照判断isValid的思路，只要遇到stack<0就remove，完了之后reverse再来一次。
这题有两种写法，面试中推荐使用以下写法。two-pass O(n); O(1)
public String removeParentheses(String s) {
if (s == null || s.length() == 0) {
return s;
}
int count = 0;
StringBuilder res = new StringBuilder();
for (int i = 0; i < s.length(); i++) { //第一遍删除多余的')'
char c = s.charAt(i);
if (c == '(') {
count++;
} else if (c == ')') {
count--;
}
if (count >= 0) {
res.append(c);
} else { //count < 0: meet the extra ')'
count = 0; //效果等于count++，因为此时count=-1
}
}
s = res.toString();
res = new StringBuilder();
count = 0;
for (int i = s.length() - 1; i >= 0; i--) { //第二遍删除多余的'('
char c = s.charAt(i);
if (c == '(') {
count--; //notice --, not ++
} else if (c == ')') {
count++;
}
if (count >= 0) {
res.append(c);
} else {
count = 0;
}
}
return res.reverse().toString();
}
public static void main(String[] args) {
RemoveInvalidParentheses test = new RemoveInvalidParentheses();
System.out.println(test.removeParentheses("(a)())()"));
System.out.println(test.removeParentheses(")(a(()"));
}
stack, two pass O(n); O(n)
/** 栈中无脑存放左括号的位置信息【通过下面的匹配，可以去除能够进行匹配的左括号，则多余的左括号一定会留在栈中】
* 当出现右括号时，看栈顶是否可以与其匹配，
* 若匹配，则栈顶出栈【说明这两个括号左右紧邻，且一定是合法顺序的样子（ XXX ）】
* 否则，说明右括号也无法匹配，右括号位置信息入栈
* 出现这种情况一般有如下两种原因
* 1. 右括号先于左括号出现，如：）a（b）【对应空栈这种corner case】
* 2. 合法的左括号已经被合法的右括号匹配掉，右括号开始比左括号多了，如：（a））（
*
* 用上述方式往栈中加入元素，最终可以得出如下结论
* 1. 栈中剩余的左括号，一定是没有右括号可以与其匹配的【原因，匹配到的都出栈了，那么，留在栈中的，一定是没有匹配成功的】
* 2. 栈中剩余的右括号，一定是"出现早了"，即前面没有剩下左括号，这个右括号就出现了
*
*/
public static String remove(String s) {
if (s == null || s.length() == 0) {
System.out.println("empty input");
return s;
}
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack.push(i);
} else if (c == ')') {
if (stack.isEmpty() || s.charAt(stack.peek()) != '(') {
stack.push(i);
} else if (s.charAt(stack.peek()) == '(') {
stack.pop();
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = s.length() - 1; i >= 0; i--) {
if (!stack.isEmpty() && stack.peek() == i) {
stack.pop();
continue;
}
sb.append(s.charAt(i));
}
return sb.reverse().toString();
}
不太推荐下面这种写法，因为用substring的最坏情况是O(n^2)。
public String removeInvalidParenthesesB(String s) { //two-pass O(n^2); O(n)
if (s == null) {
return null;
}
//left and right parentheses mean scanning the string from left to right
s = remove(s, new char[]{'(', ')'});
//right and left parentheses mean scanning the string from right to left
String reversed = remove(new StringBuilder(s).reverse().toString(), new char[]{')', '('});
return new StringBuilder(reversed).reverse().toString();
}
private String remove(String s, char[] par) {
int count = 0; //use a counter to simulate the stack
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == par[0]) {
count++;
}
if (s.charAt(i) == par[1]) {
count--;
}
if (count >= 0) {
continue;
}
s = s.substring(0, i) + s.substring(i + 1);
i--;
count++;
}
return s;
}
2.返回需要remove括号的个数