LeetCode 1249

题目描述：

给你一个由 '('、')' 和小写字母组成的字符串 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)"

思路：

使用栈来存放圆括号，遇到"("左括号就入栈，遇到")"右括号分两种情况：如果栈中有左括号就出栈，否则就是需要删除的多余右括号。等遍历整个字符串后，栈里还有多余的左括号也需要删除，将其添加到待删除的数组里。

代码如下所示：

package main

import (
    "fmt"
    "strings"
)

func minRemoveToMakeValid(s string) string {
    stack := make([]int, 0)
    toRemove := make([]int, 0)

    for i :=0;i < len(s) ;i++  {
        if string(s[i]) == "(" {
            stack = append(stack, i)
        } else if string(s[i]) == ")" && len(stack) == 0{
            toRemove = append(toRemove, i)
        } else if string(s[i]) == ")" && len(stack) >0{
            stack = stack[:len(stack) - 1]
        }
    }
    //--Initialize the string builder
    var newstring strings.Builder
    newstring.Grow(len(s) - len(toRemove))

    toRemove = append(toRemove, stack...)
    removeMap := make(map[int]bool)
    for i:=0; i< len(toRemove); i++{
        removeMap[toRemove[i]] = true
    }
    for i :=0; i < len(s); i++{
        if !removeMap[i]{
            newstring.Write([]byte{s[i]})
        }
    }
    return newstring.String()
}

func main() {
    s:= minRemoveToMakeValid("lee(t(c)o)de)")
    fmt.Println(s)
}