一、题目
给你一个由 ‘('、')' 和小写字母组成的字符串 s。
你需要从字符串中删除最少数目的 ‘(' 或者 ‘)' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
有效「括号字符串」应当符合以下 任意一条 要求：
空字符串或只包含小写字母的字符串
可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」
二、示例
))(( -》
(leetode -》 leetode
leetode) -》 leetode
(lee(to)de -》 lee(to)de
lee(to)de) -》 lee(to)de
(lee(t(c)o)de -》 lee(t(c)o)de
lee(t(c)o)de) -》 lee(t(c)o)de
|
三，解法一
public class Test {
public static void main(String[] args) {
String s1 = "))((";
System.out.println(s1 + " -》 " + minRemoveToMakeValid(s1));
String s2 = "(leetode";
System.out.println(s2 + " -》 " + minRemoveToMakeValid(s2));
String s3 = "leetode)";
System.out.println(s3 + " -》 " + minRemoveToMakeValid(s3));
String s4 = "(lee(to)de";
System.out.println(s4 + " -》 " + minRemoveToMakeValid(s4));
String s5 = "lee(to)de)";
System.out.println(s5 + " -》 " + minRemoveToMakeValid(s5));
String s6 = "(lee(t(c)o)de";
System.out.println(s6 + " -》 " + minRemoveToMakeValid(s6));
String s7 = "lee(t(c)o)de)";
System.out.println(s7 + " -》 " + minRemoveToMakeValid(s7));
}
public static String minRemoveToMakeValid(String str) {
// 初始化"("和")"的个数为0
int left = 0;
int right = 0;
// 将字符串转换为char数组
char[] chars = str.toCharArray();
// 从左到右标记多余的")"右括号
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '(') {
left++;
} else if (chars[i] == ')') {
right++;
}
if (right > left) {
chars[i] = '#';
left = right = 0;
}
}
left = right = 0;
// 从右到左标记多余的"("左括号
for (int i = chars.length - 1; i >= 0; i--) {
if (chars[i] == '(') {
left++;
} else if (chars[i] == ')') {
right++;
}
if (right < left) {
chars[i] = '#';
left = right = 0;
}
}
return String.valueOf(chars).replaceAll("#", "");
}
}
|
四、解法2
Stack.peek 与Sstack.pop 的区别
相同点：大家都返回栈顶的值。
不同点：peek 不改变栈的值(不删除栈顶的值)，pop会把栈顶的值删除。
public class Test {
public static void main(String[] args) {
String s1 = "))((";
System.out.println(s1 + " -》 " + minRemoveToMakeValid(s1));
String s2 = "(leetode";
System.out.println(s2 + " -》 " + minRemoveToMakeValid(s2));
String s3 = "leetode)";
System.out.println(s3 + " -》 " + minRemoveToMakeValid(s3));
String s4 = "(lee(to)de";
System.out.println(s4 + " -》 " + minRemoveToMakeValid(s4));
String s5 = "lee(to)de)";
System.out.println(s5 + " -》 " + minRemoveToMakeValid(s5));
String s6 = "(lee(t(c)o)de";
System.out.println(s6 + " -》 " + minRemoveToMakeValid(s6));
String s7 = "lee(t(c)o)de)";
System.out.println(s7 + " -》 " + minRemoveToMakeValid(s7));
}
public static String minRemoveToMakeValid(String str) {
// 记录要删除括号的下标，然后从后往前删除坐标
StringBuffer result = new StringBuffer(str);
Stack<Integer> stack = new Stack<>();
ArrayList<Integer> deleteRes = new ArrayList<>();
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
stack.push(i);
} else if (str.charAt(i) == ')') {
if (stack.empty()) {
deleteRes.add(i);
} else if (str.charAt(stack.peek()) == '(') {
stack.pop();
}
}
}
while (!stack.empty()) {
int temp = stack.peek();
stack.pop();
deleteRes.add(0, temp);
}
deleteRes.sort(Integer::compareTo);
for (int i = deleteRes.size() - 1; i >= 0; i--) {
result.deleteCharAt(deleteRes.get(i));
}
return result.toString();
}
}
|
|
