921. 使括号有效的最少添加

题目描述

只有满足下面几点之一，括号字符串才是有效的：

它是一个空字符串，或者
它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
它可以被写作 (A)，其中 A 是有效字符串。

给定一个括号字符串 s ，在每一次操作中，你都可以在字符串的任何位置插入一个括号

例如，如果 s = "()))" ，你可以插入一个开始括号为 "(()))" 或结束括号为 "())))" 。

返回 为使结果字符串 s 有效而必须添加的最少括号数。

示例 1：

输入：s = "())"
输出：1

示例 2：

输入：s = "((("
输出：3

提示：

1 <= s.length <= 1000
s 只包含 '(' 和 ')' 字符。

解法

方法一：贪心 + 栈

这个问题属于经典的括号匹配问题，可以使用“贪心 + 栈”来解决。

遍历字符串 $s$ 的每个字符 $c$：

若 $c$ 为左括号，直接将 $c$ 入栈；
若 $c$ 为右括号，此时如果栈不为空，且栈顶元素为左括号，则将栈顶元素出栈，表示匹配成功；否则将 $c$ 入栈。

遍历结束后，栈中剩余的元素个数即为需要添加的括号数。

时间复杂度为 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $s$ 的长度。

Python3JavaC++GoTypeScript

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        stk = []
        for c in s:
            if c == ')' and stk and stk[-1] == '(':
                stk.pop()
            else:
                stk.append(c)
        return len(stk)

class Solution {
    public int minAddToMakeValid(String s) {
        Deque<Character> stk = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == ')' && !stk.isEmpty() && stk.peek() == '(') {
                stk.pop();
            } else {
                stk.push(c);
            }
        }
        return stk.size();
    }
}

class Solution {
public:
    int minAddToMakeValid(string s) {
        string stk;
        for (char c : s) {
            if (c == ')' && stk.size() && stk.back() == '(')
                stk.pop_back();
            else
                stk.push_back(c);
        }
        return stk.size();
    }
};

func minAddToMakeValid(s string) int {
    stk := []rune{}
    for _, c := range s {
        if c == ')' && len(stk) > 0 && stk[len(stk)-1] == '(' {
            stk = stk[:len(stk)-1]
        } else {
            stk = append(stk, c)
        }
    }
    return len(stk)
}

function minAddToMakeValid(s: string): number {
    const stk: string[] = [];
    for (const c of s) {
        if (c === ')' && stk.length > 0 && stk.at(-1)! === '(') {
            stk.pop();
        } else {
            stk.push(c);
        }
    }
    return stk.length;
}

方法二：贪心 + 计数

方法一借助了栈来实现括号匹配，也可以直接通过计数来实现。

定义变量 cnt 表示当前待匹配的左括号个数，变量 ans 记录答案。初始时两个变量的值均为 $0$。

同样遍历字符串 $s$ 的每个字符 $c$：

若 $c$ 为左括号，将 cnt 的值增加 $1$；
若 $c$ 为右括号，此时如果 $cnt \gt 0$，说明当前有左括号可以匹配，将 cnt 的值减 $1$；否则说明当前右括号无法匹配，将 ans 的值增加 $1$。

遍历结束后，将 cnt 的值加到 ans 中，即为答案。

时间复杂度为 $O(n)$，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$。