1541：平衡括号字符串的最少插入次数（1759 分）

Ian

2020-08-08 约 743 字预计阅读 2 分钟次阅读

力扣第 32 场双周赛第 3 题

题目

给你一个括号字符串 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 只包含 '(' 和 ')' 。

分析

#1

1249 的升级版，只不过需要考虑更多情况。

顺序遍历遇到 ')' 时，假如 ')' 无效，前面必须执行一次添加 '(' 的操作。
假如 ')' 后面不是 ')'，还需要执行一次添加 ')' 的操作。
假如 ')' 后面是 ')'，需要跳过该 ')'
最终剩下的无效 '('，每个必须执行两次添加 ')' 的操作。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


def minInsertions(self, s: str) -> int:
    res, stack, i = 0, [], 0
    while i < len(s):
        if s[i] == '(':
            stack.append('(')
        else:
            if not stack:
                res += 1
            else:
                stack.pop()
            if i < len(s)-1 and s[i+1] == ')':
                i += 1
            else:
                res += 1
        i += 1
    return res + 2*len(stack)

364 ms

#2

注意到过程中其实只关心栈的长度。所以可以用一个变量来维护，而无需真正地进行栈操作。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


def minInsertions(self, s: str) -> int:
    res, size, i = 0, 0, 0
    while i < len(s):
        size += 1 if s[i] == '(' else -1
        if size < 0:
            res, size = res + 1, 0
        if s[i] == ')':
            if i < len(s)-1 and s[i+1] == ')':
                i += 1
            else:
                res += 1
        i += 1
    return res + 2*size

216 ms

目录

1541：平衡括号字符串的最少插入次数（1759 分）

题目

分析

#1

#2

解答