第二题是301， hard，店面也这么难？
哦对，经典题了，很高频的。dfs扫两遍。从左到右，然后从右往左。bfs的不让过的。
这题面FB必须准备到的。感觉标题换了就有点认不出来了， 直接说是 Remove Invalid Parentheses 估计马上反应过来了。
您好，想请问一下，为什么 “(()))sdf”会转变成 “sdf”呀？ 不应该是(())sdf吗？ps:祝顺利，加油！
应该是搞错了
ok thx~
这题只要找到一个解，用bfs似乎好一些
public static String balanceParens(String s) {
StringBuffer res = new StringBuffer();
int l = 0, r = 0;//num of invalid left and right
for (char c : s.toCharArray()) {
l += c == '(' ? 1 : 0;
if (l == 0) {
r += c == ')' ? 1 : 0;
} else {
l -= c == ')' ? 1 : 0;
}
}
Queue<ParenWraper> q = new LinkedList<>();
Set<String> used = new HashSet<>();
q.offer(new ParenWraper(s, l, r));
while (!q.isEmpty()) {
ParenWraper cur = q.poll();
if (isValid(cur.str)) {
return cur.str;
}
for (int i = 0; i < cur.str.length(); i++) {
if (cur.str.charAt(i) != '(' && cur.str.charAt(i) != ')') continue;
if (cur.str.charAt(i) == '(' && cur.left > 0) {
String temp = cur.str.substring(0, i) + cur.str.substring(i + 1);
if (!used.contains(temp)) {
used.add(temp);
q.offer(new ParenWraper(temp, cur.left - 1, cur.right));
}
}
if (cur.str.charAt(i) == ')' && cur.right > 0) {
String temp = cur.str.substring(0, i) + cur.str.substring(i + 1);
if (!used.contains(temp)) {
used.add(temp);
q.offer(new ParenWraper(temp, cur.left, cur.right - 1));
}
}
}
}
return "";
}
private static boolean isValid(String s) {
int count = 0;
for (char c : s.toCharArray()) {
if (c == '(') count++;
else if (c == ')') count--;
if (count < 0) return false;
}
return count == 0;
}
1 Like
哦，只要一个解啊，那bfs可行
bfs 的效率还是没有dfs 高的，无论runtime还是space
dfs能不能找到一个解就退出呢？
我bfs稍微优化了一下，不过复杂度也是没有dfs好
嗯，还是dfs吧。面试的时间有限
当然可以
对 其实有点变种 主要还是以我写的为主 不是leetcode原题
但是代码没有写完 会不会是个大问题？
是大问题
现在看第二题其实是原题，而且是高频题，叫法改了下有点坑爹（check a string to see if it’s balanced） 。这么看第二题没准备到是准备不充分啊。另外你是否用了dfs。没用的话确实凉凉了。
这第二题几乎是考FB必须要准备的高频题之一。
楼主有结果吗？
反正我只需要把他给我的test case给写过就可以了呗，其他的一时半会也想不全
想出多个test case也是面试的考察点，这个很重要
remove invalid 括号的问题，能不能用stack遍历一遍，标记出有问题的括号(孤独的右括号或者最后栈里的左括号) 然后移除他们?
目测可行，你写个代码测一下就知道了