Java移除无效括号的方法实现

Java移除无效括号的方法实现

目录一、题目二、示例三、解法1四、解法2

一、题目

给你一个由 ‘('、')' 和小写字母组成的字符串 s。

你需要从字符串中删除最少数目的 ‘(' 或者 ‘)' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。

有效「括号字符串」应当符合以下 任意一条 要求：

空字符串或只包含小写字母的字符串

可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」cBLVCNDYu

可以被写作 (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

三、解法1

public class Test {

public static void main(String[] args) {

String s1 = "))((";

System.out.println(s1 + " -》 " + minRemoveToMakeValid(s1));

String s2 = "(leetode";

System.out.println(s2 + " -》 " + minRemovehttp://ToMakeValid(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 stack = new Stack<>();

ArrayList 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();

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。