这是一道面经题目。
就是给你一个invalid parenthese, 删掉一些，输出其中一种valid的情况。
难度低于
- Remove Invalid Parentheses
http://www.jianshu.com/p/107a8e166351
My code:
import java.util.ArrayList;
import java.util.HashSet;
public class Solution {
public String balance(String s) {
if (s == null || s.length() == 0)
return s;
int left = 0;
int right = 0;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char curr = s.charAt(i);
if (curr == '(') {
left++;
sb.append('(');
}
else if (curr == ')' && left > right) {
right++;
sb.append(')');
}
}
s = sb.toString();
sb = new StringBuilder();
left = 0;
right = 0;
for (int i = s.length() - 1; i >= 0; i--) {
char curr = s.charAt(i);
if (curr == ')') {
right++;
sb.append(')');
}
if (curr == '(' && right > left) {
left++;
sb.append('(');
}
}
return sb.reverse().toString();
}
public static void main(String[] args) {
Solution test = new Solution();
System.out.println(test.balance("()())()"));
}
}
Anyway, Good luck, Richardo!
