带平衡括号的子串

Question

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

我能想到这个问题的唯一解决方案是蛮力，这需要 n^3 次。有没有更快的解决方案 possible.If 那么我也想知道该方法的构建。

Answer 1

我做了一个简单的算法来解决你的问题。请注意，它不会查找嵌套的平衡括号。

function TestAlgorithm(testString, resultCounter)
{
    if (!resultCounter)
        resultCounter = 0;

    var startIndex = testString.indexOf('(');

    if (startIndex === -1)
        return resultCounter;

    var endIndex = testString.indexOf(')', startIndex)

    if (endIndex === -1)
        return resultCounter;

    var newTestString = testString.substring(endIndex);

    return TestAlgorithm(newTestString, ++resultCounter);
}

Answer 2

假设最终结果是一个整数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最后的自增操作只是为了不遗漏最外层

Answer 3

范围内的每个子字符串都以“(”开头。所以我的非递归方法是：

total = 0
while string is not empty {
    count valid substrings beginning here -- add to total
    trim leading '(' and trailing ')' from string
    trim leading ')' and trailing '(' from string if present
}

count valid substrings beginning here 可以通过一个字符一个字符地逐步执行，在看到“(”时递增计数器，在看到“)”时递减计数器来完成。当递减结果为零时，您位于平衡子串的结尾 ')'。

带平衡括号的子串

substrings with Balanced parentheses

string

algorithm

parentheses