平衡括号字符串的最少插入次数

难度: Medium

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

Submission

运行时间: 64 ms

内存: 17.0 MB

class Solution:
    def minInsertions(self, s: str) -> int:
        s = s.replace("))", "*")
        result = s.count(")")
        s = s.replace(")", "*")
        while "(*" in s:
            s = s.replace("(*", "")
        print(s)
        result += s.count("*") + 2 * s.count("(")
        return result

Explain

题解首先通过将字符串中的连续两个 ')' 替换为一个 '*' 简化表示，这样每个 '*' 代表一个有效的 '))'。然后，计算剩余的单独 ')' 的数量，因为这些 ')' 是无法匹配的，需要额外的 '(' 来匹配。接着，将这些无法匹配的 ')' 也替换为 '*'。然后，通过循环消除形如 '(*' 的模式，这种模式表示一个 '(' 直接匹配了后面的 '))'。最后，统计剩余的 '*' 和 '(' 的数量，每个 '*' 需要一个 ')' 来匹配，每个 '(' 需要两个 ')' 来匹配。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minInsertions(self, s: str) -> int:
        s = s.replace('))', '*')  # 把所有的 '))' 替换为 '*' 简化处理
        result = s.count(')')  # 计算剩余的单独 ')' 的个数
        s = s.replace(')', '*')  # 将剩余的 ')' 也替换为 '*'
        while '(*' in s:  # 循环消除 '(*' 模式，表示一个 '(' 匹配了一个 '*'
            s = s.replace('(*', '')
        print(s)
        result += s.count('*') + 2 * s.count('(')  # '*' 需要一个 ')' 来匹配，'(' 需要两个 ')'
        return result

Explore

在算法中，将连续的两个 ')' 替换为一个 '*' 是为了简化对有效配对的处理。在问题中，每个 '(' 可以关闭两个 ')'，因此通过将每对 ')' 视为一个单元（'*'），可以更直观和简单地处理和计算需要的插入次数。这种替换有助于将问题转化为更简单的形式，即只需关注单一类型的配对 ('*' 与 '(') 而不是多种类型的 ')'，从而减少错误并提高算法的可读性和实现的简洁性。

在替换连续的两个 ')' 为 '*' 后，可能会剩下一些单独的 ')'。这些单独的 ')' 无法形成有效的配对，因此需要额外的 '(' 来与之匹配。算法将这些单独的 ')' 也转换为 '*'，使得后续处理统一且简单，即处理所有的 '*' 都需要配对的 '('。这样做减少了处理不同情况的复杂性，允许算法统一处理所有需要 ')' 的情况。

'(*' 模式代表一个 '(' 后紧接着一个 '*'（即 '))'），表示这个 '(' 已经匹配了紧随其后的两个 ')'。在算法中，循环消除这种模式的目的是减少未匹配的 '(' 和 '*'，从而准确计算出需要额外插入的字符数。每次消除一个 '(*' 模式，意味着一个 '(' 已经成功匹配了两个 ')'，因此这两个字符不再需要额外的配对，可以从字符串中移除，简化后续的计算。

在进行了上述替换和消除操作后，字符串中可能还剩下一些未匹配的 '(' 和 '*'. 由于每个 '*' 代表一个已经成对的 ')'，因此每个 '*' 需要一个 ')' 来完成配对。而每个 '(' 需要两个 ')' 来匹配，因为在原始问题定义中，一个 '(' 旨在匹配两个 ')'. 因此，计算最少插入次数时，对于每个剩余的 '*'，增加一个 ')' 的需求；对于每个 '('，增加两个 ')' 的需求。这样计算出的总数即为需要插入的 ')' 数量，以确保所有的括号都能正确配对。