Skip to main content

1541. 平衡括号字符串的最少插入次数 [medium]

1541. 平衡括号字符串的最少插入次数 [medium]​

https://leetcode-cn.com/problems/minimum-insertions-to-balance-a-parentheses-string/

给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：

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

比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。

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

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

示例 1：

输入：s = "(()))"
输出：1
解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。

示例 2：

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

示例 3：

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

示例 4：

输入：s = "(((((("
输出：12
解释：添加 12 个 ')' 得到平衡字符串。

示例 5：

输入：s = ")))))))"
输出：5
解释：在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ，字符串变成平衡字符串 "(((())))))))" 。

提示：

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

通过次数2,146 | 提交次数5,265

First Try​

2020-08-08

周赛题目。括号题目的变种，要求一个左括号对应两个右括号，使用次数统计可以解决。

遇到右括号的时候，查看是否是两个连续的右括号，如果不是先进行插入右括号凑齐。 一边遍历一边对index进行跳转，然后判断总和是否为0继续进行左括号的补齐。


class Solution:
    def minInsertions(self, s: str) -> int:
        mop = {
            "(": 2,
            ")": -1
        }
        z = 0 
        counter = 0
        i = 0 
        while i < len(s):
            # z += mop[s[i]]
            if s[i] == ")":  # 首先")"必须凑成一对才行
                if i + 1 < len(s) and s[i + 1] == "(":
                    counter += 1 
                    i += 1
                elif i + 1 < len(s) and s[i + 1] == ")": # one pair
                    i += 2
                elif i + 1 == len(s):
                    counter += 1 
                    i += 1
                z += -2 
            elif s[i] == "(":
                z += 2
                i += 1
            # 然后再来考虑是否偏差的问题
            if z < 0:
                counter += 1 # insert "("
                z = 0 

        if z > 0:
            counter += z
        return counter
  • 执行用时：352 ms, 在所有 Python3 提交中击败了15.16%的用户
  • 内存消耗：14.2 MB, 在所有 Python3 提交中击败了44.25%的用户