h*********i
发帖数: 2605 | 1 1.题主用的是BFS貌似就是leetcode上的高分解答：
https://discuss.leetcode.com/topic/28827/share-my-java-bfs-solution
肯定是蛮力了，但好像一般人也没有更优解
2.还有steyang1990提到简化版。请教是什么简化版？ | s**x
发帖数: 7506 | 2 最优解的思路 最核心的就是 跟验证 valid parenthesis string 一样， 保证 左括号
数始终大于右括号数， 从右向左反之。 用一个 counter 就应该能搞定。 | s*********0
发帖数: 10 | 3 仅此而已，no trick ，
public String lc301(String input) {
char[]inputt = input.toCharArray();
StringBuilder s = new StringBuilder();
StringBuilder res = new StringBuilder();
int open = 0;
for (char i : inputt) {
if (i =='(') {
open++;
s.append(i);
}else if (i ==')') {
if(open >0) {
s.append(i);
open--;
}
}else {
s.append(i);
}
}
open = 0;
for (int i = s.length() -1 ; i >=0 ; i--) {
if (s.charAt(i) ==')') {
open++;
res.append(s.charAt(i));
}else if(s.charAt(i) =='(') {
if (open >0 ){
res.append(s.charAt(i));
open--;
}
}else {
res.append(s.charAt(i));
}
}
return new String(res.reverse());
}
| s**x
发帖数: 7506 | 4 nRight =
nLeft =
right>
normally nLeft++, nRight-- accordingly.
for each ( or ), we should be able determine they can be kept or removed
purely based on nLeft and nRight.
that is it. twice scan, const space. | t**********u
发帖数: 1 | 5 简化版只输出一个答案可以用counter做。
如果是301原题输出所有解那就要dfs了，dfs比bfs省空间，并且不需要set来去重，看
起来更elegant。DFS之前要先count一下需要删除多少个。时间复杂度是O(N^k), k是需
要删除的括号数。当然是需要删除的越多，解就越多，复杂度就越高。上code：
class Solution {
public List removeInvalidParentheses(String s) {
int leftRemove = 0;
int rightRemove = 0;
int open = 0;
for (int i = 0; i < s.length(); ++i) {
char cur = s.charAt(i);
if (cur == '(') {
open++;
} else if (cur == ')') {
if (open <= 0) {
rightRemove++;
} else {
open--;
}
}
}
int close = 0;
for (int i = s.length() - 1; i >= 0; --i) {
char cur = s.charAt(i);
if (cur == ')') {
close++;
} else if (cur == '(') {
if (close <= 0) {
leftRemove++;
} else {
close--;
}
}
}
List rst = new ArrayList<>();
dfs(s, 0, leftRemove, rightRemove, new boolean[s.length()], rst);
return rst;
}
private void dfs(String s, int start, int leftRemove, int rightRemove,
boolean[] removeMap, List rst) {
if (start >= s.length()) {
if (leftRemove == 0 && rightRemove == 0 && isValid(s, removeMap)
) {
rst.add(buildString(s, removeMap));
}
return;
}
char cur = s.charAt(start);
if (cur == '(') {
if (leftRemove > 0 && (start == 0 || s.charAt(start - 1) != '('
|| removeMap[start - 1])) {
removeMap[start] = true;
dfs(s, start + 1, leftRemove - 1, rightRemove, removeMap,
rst);
removeMap[start] = false;
}
} else if (cur == ')') {
if (rightRemove > 0 && (start == 0 || s.charAt(start - 1) != ')'
|| removeMap[start - 1])) {
removeMap[start] = true;
dfs(s, start + 1, leftRemove, rightRemove - 1, removeMap,
rst);
removeMap[start] = false;
}
}
dfs(s, start + 1, leftRemove, rightRemove, removeMap, rst);
}
private boolean isValid(String s, boolean[] removeMap) {
int open = 0;
for (int i = 0; i < s.length(); ++i) {
if (removeMap[i]) {
continue;
}
if (s.charAt(i) == '(') {
open++;
} else if (s.charAt(i) == ')') {
if (open <= 0) {
return false;
}
open--;
}
}
return open == 0;
}
private String buildString(String s, boolean[] removeMap) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); ++i) {
if (!removeMap[i]) {
sb.append(s.charAt(i));
}
}
return sb.toString();
}
} | c***e
发帖数: 14 | 6 赞！！！
这个版终于又回来了
【在 t**********u 的大作中提到】
: 简化版只输出一个答案可以用counter做。
: 如果是301原题输出所有解那就要dfs了，dfs比bfs省空间，并且不需要set来去重，看
: 起来更elegant。DFS之前要先count一下需要删除多少个。时间复杂度是O(N^k), k是需
: 要删除的括号数。当然是需要删除的越多，解就越多，复杂度就越高。上code：
: class Solution {
: public List removeInvalidParentheses(String s) {
: int leftRemove = 0;
: int rightRemove = 0;
: int open = 0;
: for (int i = 0; i < s.length(); ++i) {
| g******n
发帖数: 253 | 7 牛！本版一股清流！
看来这个解法是onsite的难度。如果找一个解，可能就是电面的难度吧。对不？
要是电面能够写出来下面的，那直接hire进去了事了。 ：）
【在 t**********u 的大作中提到】
: 简化版只输出一个答案可以用counter做。
: 如果是301原题输出所有解那就要dfs了，dfs比bfs省空间，并且不需要set来去重，看
: 起来更elegant。DFS之前要先count一下需要删除多少个。时间复杂度是O(N^k), k是需
: 要删除的括号数。当然是需要删除的越多，解就越多，复杂度就越高。上code：
: class Solution {
: public List removeInvalidParentheses(String s) {
: int leftRemove = 0;
: int rightRemove = 0;
: int open = 0;
: for (int i = 0; i < s.length(); ++i) {
| g******n
发帖数: 253 | 8 复杂度的估计中N左右括号中较多数量的那个括号的总数吗？
如果是这样，那么复杂度是不是O（N choose K）呢？ 如果K<
区别了。
【在 t**********u 的大作中提到】
: 简化版只输出一个答案可以用counter做。
: 如果是301原题输出所有解那就要dfs了，dfs比bfs省空间，并且不需要set来去重，看
: 起来更elegant。DFS之前要先count一下需要删除多少个。时间复杂度是O(N^k), k是需
: 要删除的括号数。当然是需要删除的越多，解就越多，复杂度就越高。上code：
: class Solution {
: public List removeInvalidParentheses(String s) {
: int leftRemove = 0;
: int rightRemove = 0;
: int open = 0;
: for (int i = 0; i < s.length(); ++i) {
| w*******o
发帖数: 113 | 9 public class Solution {
public List removeInvalidParentheses(String s) {
List res = new ArrayList<>();
Queue queue = new LinkedList<>();
Set checked = new HashSet<>();
boolean found = false;
int max = 0;
queue.add(s);
while (!queue.isEmpty()) {
String t = queue.remove();
if (isValid(t)) {
found = true;
if (t.length() >= max && !res.contains(t)) {
max = t.length();
res.add(t);
}
}
if (found) continue;
for (int i = 0; i < t.length(); i++) {
String sub1 = t.substring(0, i);
String sub2 = t.substring(i + 1, t.length());
String temp = sub1.concat(sub2);
if (!checked.contains(temp)) {
queue.add(temp);
checked.add(temp);
}
}
}
return res;
}
private 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) == ')') {
if (count == 0) return false;
else count--;
}
}
return count == 0;
}
} | j*****g
发帖数: 254 | 10 I don't think so. There is something called onsite interview.
【在 g******n 的大作中提到】
: 牛！本版一股清流！
: 看来这个解法是onsite的难度。如果找一个解，可能就是电面的难度吧。对不？
: 要是电面能够写出来下面的，那直接hire进去了事了。 ：）
| n*******4
发帖数: 20 | 11 最优解
Time complexity O(n), space complexity O(1)
void removeUtil(string &s, string &res, string par) {
int stack=0;
int left=0;
for (int i=0;i
if (s[i]==par[0]) stack++;
if (s[i]==par[1]) stack--;
if (stack>=0)
res[left++] = s[i];
}
res.resize(left);
}
void removeInvalid(string s, string &res) {
res.resize(s.length());
removeUtil(s, res, "()");
reverse(res.begin(), res.end());
removeUtil(res, res,")(");
reverse(res.begin(), res.end());
} |
|
