LC301. 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 ).
Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]
想法还是比较简单，如果多余“）”，就随便移除哪一个”)”, 如果多余”(“, 就随便移除不是第一个”(“. 但是如果遇到连续的会产生重复结果，所以连续的就移除第一个，然后还要记录已经处理到的位置。discuss的方法好简单，只要reverse输入就可以了👍
public class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> res = new ArrayList<String>();
remove(s, res, 0, 0, new char[]{'(', ')'});
return res;
}
// i is where we begin check, j is where we begin to delete
public void remove(String s, List<String> res, int last_i, int last_j, char[] pair){
int count = 0;
for(int i = last_i; i < s.length(); i++){
if(s.charAt(i) == pair[0]) count++;
if(s.charAt(i) == pair[1]) count--;
if(count < 0){
for(int j = last_j; j <= i; j++){
// if ))))) remove first one
if(s.charAt(j) == pair[1] && (j == last_j || s.charAt(j-1) != pair[1])){
// use i, j cuz we deduct one digit
remove(s.substring(0, j)+s.substring(j+1), res, i, j, pair);
}
} // for j
return;
} // if
} // for i
String reverse = new StringBuilder(s).reverse().toString();
// finish left to right, need reverse
if(pair[0] == '('){
remove(reverse, res, 0, 0, new char[]{')', '('});
}else{
// finish right to left
res.add(reverse);
}
return;
}
}
大神关于时间复杂度的解释.膜拜
The program only generates valid answers. Every path in the search generates one valid answer. The whole search space is a tree with k leaves. The number of nodes in the tree is roughly O(k). But this is not always true, for example a degenerated tree.
To generate one node it requires O(n) time from the string concatenation among other things. So roughly O(nk). Accurately O(nm) where m is the total “number of recursive calls” or “nodes in the search tree”. Then you need to relate m to n in the worst case.