Java：移除无效的括号

- 日理万妓 2023-01-14 14:56 123阅读 0赞

## 一、题目 ##

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

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

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

1.  空字符串或只包含小写字母的字符串
2.  可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
3.  可以被写作 (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 + " -》 " + 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 的区别
> 
> 1.  相同点：大家都返回栈顶的值。
> 2.  不同点：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();
    	}
    
    }