Medium

题目描述

当且仅当以下情况时，括号字符串才有效：

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

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

例如，如果 s = “())"，你可以插入一个开括号变成 “(())” 或者插入一个闭括号变成 “()))))"。

返回使 s 有效所需的最少插入次数。

示例 1：

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

示例 2：

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

提示：

  • 1 <= s.length <= 1000
  • s[i] 是 ‘(’ 或 ‘)’

解题思路

这道题要求计算使括号字符串有效所需的最少添加次数。我们可以使用贪心策略来解决。

核心思路： 遍历字符串，维护两个计数器：

  1. open：记录未匹配的左括号数量
  2. close：记录无法匹配的右括号数量

算法流程：

  • 遇到 (：增加 open 计数
  • 遇到 )：
    • 如果有未匹配的左括号（open > 0），则匹配一对，open 减1
    • 否则这是一个多余的右括号，close 增加1

为什么这样可行？

  • open 记录了需要添加右括号的数量
  • close 记录了需要添加左括号的数量
  • 总的添加次数就是 open + close

这种贪心策略是最优的，因为我们总是优先匹配已有的括号，只有在无法匹配时才计入需要添加的数量。

时间复杂度： O(n)，只需遍历一次字符串 空间复杂度： O(1)，只使用常数额外空间

代码实现

class Solution {
public:
    int minAddToMakeValid(string s) {
        int open = 0, close = 0;
        
        for (char c : s) {
            if (c == '(') {
                open++;
            } else {
                if (open > 0) {
                    open--;
                } else {
                    close++;
                }
            }
        }
        
        return open + close;
    }
};

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        open_count = 0
        close_count = 0
        
        for c in s:
            if c == '(':
                open_count += 1
            else:
                if open_count > 0:
                    open_count -= 1
                else:
                    close_count += 1
        
        return open_count + close_count

public class Solution {
    public int MinAddToMakeValid(string s) {
        int open = 0, close = 0;
        
        foreach (char c in s) {
            if (c == '(') {
                open++;
            } else {
                if (open > 0) {
                    open--;
                } else {
                    close++;
                }
            }
        }
        
        return open + close;
    }
}

var minAddToMakeValid = function(s) {
    let open = 0;
    let close = 0;
    
    for (let char of s) {
        if (char === '(') {
            open++;
        } else if (char === ')') {
            if (open > 0) {
                open--;
            } else {
                close++;
            }
        }
    }
    
    return open + close;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是字符串长度，需要遍历字符串一次
空间复杂度O(1)，只使用常数个变量存储计数器

相关题目