string - 带平衡括号的子串

Question

我的 friend 在一次采访中被问到以下问题:给定一个仅由“(”和“)”组成的字符串。找到带平衡括号的子串总数注意:输入字符串已经平衡。

我能想到这个问题的唯一解决方案是蛮力，这需要 n^3 时间。是否有更快的解决方案。如果有，那么我也想知道该方法的构建。

Answer 1

假设最后的结果是一个整数R。你应该在字符串上从左到右扫描然后，你应该保留一个堆栈Z，并在从左到右扫描时更新它。

您应该首先将 0 压入 Z。当您在索引 i 处遇到 '(' 时，您应该将 0 压入 S。当您在索引 i 处遇到 ')' 时，您应该将 R 递增 (T * ( T+1)/2), T 是 Z 的顶部元素。然后你应该弹出 T，并将 新的顶部元素 递增 1。

一旦扫描完成，您应该将 R 再递增一次 (T * (T+1)/2)，因为在 Z 中仍然有我们最初放入的元素 T。

使用堆栈 Z 的扫描应该花费线性时间。下面是一个效率不高的 Python 实现，希望它易于理解。

def solve(s):
    R = 0
    Z = [0]
    for i in range(0, len(s)):
        if s[i] == '(':
            Z.append(0)
        else:
            R += Z[-1] * (Z[-1] + 1) / 2
            Z = Z[:-1]
            Z[-1] += 1
    R += Z[-1] * (Z[-1] + 1) / 2
    return R

递增 R 背后的想法如下。基本上，您会保留连续 同级平衡弦的数量，直到即将超出该级别。然后，当您即将进入更高级别时(即当我们知道不会有任何其他相同级别且连续的子串时，我们更新解决方案。

T * (T + 1)/2 的值如果你从不同的角度考虑间隔就可以理解。让我们枚举从 1 到 T 的那些连续的同级平衡子串。现在，使用这些选择平衡子串基本上是为我们的较大子串选择起点和终点。如果我们选择子串 #1 作为起点，那么还有 T 个其他子串可以作为终点。对于#2，有 (T-1)，依此类推。基本上，我们可以选择 T*(T+1)/2 个不同的间隔作为有效的平衡子串，这就是我们将 R 递增该值的原因。

我们对 R 应用的最终增量操作只是为了不遗漏最外层。