1249. 移除无效的括号

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

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

请返回任意一个合法字符串。

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

空字符串或只包含小写字母的字符串
可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」

示例 1：

输入：s = "lee(t(c)o)de)"
输出："lee(t(c)o)de"
解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。
示例 2：

输入：s = "a)b(c)d"
输出："ab(c)d"
示例 3：

输入：s = "))(("
输出：""
解释：空字符串也是有效的
示例 4：

输入：s = "(a(b(c)d)"
输出："a(b(c)d)"

解题思路：这道题的解题思路和根据左右括号匹配来判断字符串是否合法是一样的，都是用栈的思路解决问题，遇到左括号，则将索引压入堆栈；遇到右括号，则判断堆栈是否空；此时，如果堆栈非空，则弹出栈顶索引对应的左括号，否则，就把当前的右括号索引压入堆栈。最后把栈中所有索引对应的括号从原来的字符串中移除，这里堆栈有个明显的特征，就是右括号一定在左括号之前。

代码 t60 s75 java

class Solution {
    public String minRemoveToMakeValid(String s) {
        Stack<Integer> st = new Stack<>();
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i)==‘(‘) st.push(i);
            if(s.charAt(i)==‘)‘){
                if(!st.isEmpty() && s.charAt(st.peek())==‘(‘) st.pop();
                else st.push(i);
            }
        }
        StringBuffer sb = new StringBuffer(s);
        while(!st.isEmpty()){
            sb.deleteCharAt(st.pop());
        }
        return sb.toString();
    }
}

这里就注意一个方法StringBuffer.deleteCharAt(int i)，删除指定位置的字符。

代码 t55 s60 cpp

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<int> st;
        for(int i=0; i<s.size(); i++){
            if(s[i] == ‘(‘){
                st.push(i);
            }
            if(s[i] == ‘)‘){
                if(!st.empty() && s[st.top()]==‘(‘){
                    st.pop();
                }
                else{
                    st.push(i);
                }
            }
        }
        while(!st.empty()){
            s.erase(st.top(), 1);
            st.pop();
        }
        return s;
    }
}

1249. 移除无效的括号

原文：https://www.cnblogs.com/zhengxch/p/14861363.html