1遗增、題目描述：
Leetcode 1249. Minimum Remove to Make Valid Parentheses 移除無效的括號(hào)
Given a string s of '(' , ')' and lowercase English characters.
Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.
Formally, a parentheses string is valid if and only if:
It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.
給你一個(gè)由 '('、')' 和小寫字母組成的字符串 s脱盲。
你需要從字符串中刪除最少數(shù)目的 '(' 或者 ')' （可以刪除任意位置的括號(hào))广匙，使得剩下的「括號(hào)字符串」有效。
請返回任意一個(gè)合法字符串。
有效「括號(hào)字符串」應(yīng)當(dāng)符合以下 任意一條 要求：
空字符串或只包含小寫字母的字符串
可以被寫作 AB（A 連接 B）的字符串夫椭，其中 A 和 B 都是有效「括號(hào)字符串」
可以被寫作 (A) 的字符串，其中 A 是一個(gè)有效的「括號(hào)字符串」
2氯庆、解題思路：
使用棧來解決括號(hào)匹配的問題
3蹭秋、代碼
class Solution {
public String minRemoveToMakeValid(String s) {
// 使用StringBuilder保存結(jié)果
StringBuilder sb = new StringBuilder();
// 記錄左括號(hào)的位置扰付，用于判斷右括號(hào)是否匹配
Stack<Integer> stack = new Stack<>();
// 記錄需要移除的字符的下標(biāo)
Set<Integer> toRemove = new HashSet<>();
// 遍歷字符串
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
// 左括號(hào)入棧
stack.push(i);
} else if (c == ')') {
if (stack.isEmpty()) {
// 沒有左括號(hào)匹配，標(biāo)記為需要移除的字符
toRemove.add(i);
} else {
// 彈出棧頂?shù)淖罄ㄌ?hào)
stack.pop();
}
}
}
// 標(biāo)記未匹配的左括號(hào)
while (!stack.isEmpty()) {
toRemove.add(stack.pop());
}
// 構(gòu)造結(jié)果字符串
for (int i = 0; i < s.length(); i++) {
if (!toRemove.contains(i)) {
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}
class Solution {
public String minRemoveToMakeValid(String s) {
// 將字符串轉(zhuǎn)化為字符數(shù)組
char[] chars = s.toCharArray();
Stack<Integer> stack = new Stack<>(); // 用棧來存儲(chǔ)左括號(hào)的下標(biāo)
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '(') {
stack.push(i); // 如果是左括號(hào)仁讨，將其下標(biāo)壓入棧中
} else if (chars[i] == ')') {
if (!stack.empty()) {
stack.pop(); // 如果是右括號(hào)羽莺，判斷棧是否為空，不為空則彈出棧頂元素
} else {
chars[i] = '*'; // 如果棧為空洞豁，則將右括號(hào)替換為'*'
}
}
}
while (!stack.empty()) {
chars[stack.pop()] = '*'; // 處理多余的左括號(hào)盐固，將其替換為'*'
}
return new String(chars).replaceAll("\\*", ""); // 將所有的'*'替換為空字符
}
}
