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

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

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

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

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

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

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

示例 2：
输入：s = "((("
输出：3

解题思路

输入：一个只包含 '(' 和 ')' 的字符串 s

输出：返回使括号字符串有效所需添加的最少括号数

本题是典型的 合法括号栈 问题，适合用栈模拟括号的匹配过程。

1. 定义一个栈 stack 用于存放未匹配的左括号 '('；

2. 遍历字符串中的每个字符：

   • 如果是 '('，直接入栈，表示等待匹配；

   • 如果是 ')'：

     • 若栈不为空，说明有可匹配的左括号，弹出一个；
     • 若栈为空，说明没有可匹配的左括号，需要补一个左括号，count += 1；

3. 遍历完成后：

   • count 记录了多余的右括号需要补的左括号数量；
   • len(stack) 表示未匹配的左括号数量，需要补相应数量的右括号。

代码实现

python

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        stack = []  # 用栈保存未匹配的左括号
        count = 0   # 统计需要额外添加的右括号数量

        # 遍历字符串中的每个括号
        for c in s:
            if c == '(':  
                # 左括号直接入栈，等待匹配
                stack.append(c)
            else:  # 遇到右括号 ')'
                if stack:
                    # 有未匹配的左括号，匹配成功，弹出一个
                    stack.pop()
                else:
                    # 没有左括号可匹配，说明需要额外添加一个左括号
                    count += 1

        # 遍历结束后：
        # - count 是需要补的左括号数量（用来匹配多余的右括号）
        # - len(stack) 是剩下未匹配的左括号数量，需要补等量的右括号
        return count + len(stack)

javascript

const minAddToMakeValid = function(s) {
    const stack = [];
    let count = 0;

    for (let c of s) {
        if (c == '(') {
            stack.push(c);
        } else {
            if (stack.length) {
                stack.pop();
            } else {
                count ++;
            }
        }
    }

    return count + stack.length;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

链接

921 国际版

921 中文版