Medium

题目描述

给你一个只包含字符 ‘(’ 和 ‘)’ 的括号字符串 s。一个括号字符串被称为平衡的当且仅当：

  • 任何左括号 ‘(’ 必须对应两个连续的右括号 ‘))’。
  • 左括号 ‘(’ 必须在对应的两个连续右括号 ‘))’ 之前。

换句话说，我们可以认为 ‘(’ 是开括号，’))’ 是闭括号。

  • 例如 “())"、”())(())))" 和 “(())())))” 都是平衡的，")()"、"()))" 和 “(()))” 都是不平衡的。

你可以在任意位置插入字符 ‘(’ 和 ‘)’ 使字符串平衡。

请返回让 s 平衡所需的最少插入次数。

示例 1：

输入：s = "(()))"
输出：1
解释：第二个 '(' 有两个匹配的 '))'，但是第一个 '(' 只有一个匹配的 ')'。我们需要在字符串末尾添加一个 ')' 得到 "(())))"，这样字符串就平衡了。

示例 2：

输入：s = "())"
输出：0
解释：字符串已经平衡了。

示例 3：

输入：s = "))())("
输出：3
解释：添加 '(' 去匹配最开头的 '))'，添加 '))' 去匹配最后一个 '('。

提示：

  • 1 <= s.length <= 10^5
  • s 只包含 ‘(’ 和 ‘)’

解题思路

这是一道关于括号匹配的变种题目。关键在于理解题目的平衡规则：每个左括号需要匹配两个连续的右括号。

解题思路：

我们可以使用贪心策略来解决这个问题：

  1. 遍历字符串，维护一个变量 need 表示当前需要的右括号数量
  2. 遇到左括号 ‘(’ 时，需要增加 2 个右括号的需求
  3. 遇到右括号 ‘)’ 时，需要减少 1 个右括号的需求
  4. 如果当前需求为 0 但遇到了右括号，说明缺少左括号，需要插入

具体实现：

  • 当遇到 ‘(’ 时，need += 2
  • 当遇到 ‘)’ 时：
    • 如果 need > 0，说明有左括号可以匹配，need -= 1
    • 如果 need = 0，说明这个右括号无法匹配，需要插入一个左括号，然后 need = 1（因为新插入的左括号需要 2 个右括号，当前这个右括号算 1 个）

最后，如果 need > 0，说明还有未匹配的左括号，需要插入对应数量的右括号。

这种方法的优势是只需要一次遍历，时间复杂度为 O(n)，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int minInsertions(string s) {
        int need = 0;  // 需要的右括号数量
        int insertions = 0;  // 需要插入的字符数量
        
        for (char c : s) {
            if (c == '(') {
                need += 2;
            } else {  // c == ')'
                if (need > 0) {
                    need--;
                } else {
                    // 需要插入一个左括号
                    insertions++;
                    need = 1;  // 新插入的左括号需要2个右括号，当前这个右括号算1个
                }
            }
        }
        
        return insertions + need;
    }
};

class Solution:
    def minInsertions(self, s: str) -> int:
        need = 0  # 需要的右括号数量
        insertions = 0  # 需要插入的字符数量
        
        for c in s:
            if c == '(':
                need += 2
            else:  # c == ')'
                if need > 0:
                    need -= 1
                else:
                    # 需要插入一个左括号
                    insertions += 1
                    need = 1  # 新插入的左括号需要2个右括号，当前这个右括号算1个
        
        return insertions + need

public class Solution {
    public int MinInsertions(string s) {
        int need = 0;  // 需要的右括号数量
        int insertions = 0;  // 需要插入的字符数量
        
        foreach (char c in s) {
            if (c == '(') {
                need += 2;
            } else {  // c == ')'
                if (need > 0) {
                    need--;
                } else {
                    // 需要插入一个左括号
                    insertions++;
                    need = 1;  // 新插入的左括号需要2个右括号，当前这个右括号算1个
                }
            }
        }
        
        return insertions + need;
    }
}

var minInsertions = function(s) {
    let open = 0;
    let insertions = 0;
    let i = 0;
    
    while (i < s.length) {
        if (s[i] === '(') {
            open++;
        } else {
            if (i + 1 < s.length && s[i + 1] === ')') {
                i++;
                if (open > 0) {
                    open--;
                } else {
                    insertions++;
                }
            } else {
                insertions++;
                if (open > 0) {
                    open--;
                } else {
                    insertions++;
                }
            }
        }
        i++;
    }
    
    insertions += open * 2;
    return insertions;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需要遍历字符串一次，n 为字符串长度
空间复杂度O(1)只使用了常数个变量存储状态

相关题目