栈｜ Leetcode 1249

Leetcode 分类刷题 —— 栈（Stack）

1、题目描述：

Leetcode 1249. Minimum Remove to Make Valid Parentheses 移除无效的括号

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.

给你一个由 '('、')' 和小写字母组成的字符串 s。
你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
请返回任意一个合法字符串。
有效「括号字符串」应当符合以下 任意一条 要求：
空字符串或只包含小写字母的字符串
可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」

2、解题思路：

使用栈来解决括号匹配的问题

3、代码

class Solution {
    public String minRemoveToMakeValid(String s) {
        // 使用StringBuilder保存结果
        StringBuilder sb = new StringBuilder();
        // 记录左括号的位置，用于判断右括号是否匹配
        Stack<Integer> stack = new Stack<>();
        // 记录需要移除的字符的下标
        Set<Integer> toRemove = new HashSet<>();
        
        // 遍历字符串
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                // 左括号入栈
                stack.push(i);
            } else if (c == ')') {
                if (stack.isEmpty()) {
                    // 没有左括号匹配，标记为需要移除的字符
                    toRemove.add(i);
                } else {
                    // 弹出栈顶的左括号
                    stack.pop();
                }
            }
        }
        
        // 标记未匹配的左括号
        while (!stack.isEmpty()) {
            toRemove.add(stack.pop());
        }
        
        // 构造结果字符串
        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) {
        // 将字符串转化为字符数组
        char[] chars = s.toCharArray();
        Stack<Integer> stack = new Stack<>(); // 用栈来存储左括号的下标
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(') {
                stack.push(i); // 如果是左括号，将其下标压入栈中
            } else if (chars[i] == ')') {
                if (!stack.empty()) {
                    stack.pop(); // 如果是右括号，判断栈是否为空，不为空则弹出栈顶元素
                } else {
                    chars[i] = '*'; // 如果栈为空，则将右括号替换为'*'
                }
            }
        }
        while (!stack.empty()) {
            chars[stack.pop()] = '*'; // 处理多余的左括号，将其替换为'*'
        }
        return new String(chars).replaceAll("\\*", ""); // 将所有的'*'替换为空字符
    }
}