在Python中找到给定字符串中最长有效括号的长度

在处理文本数据时，可能会遇到一些包含括号的字符串。有时我们需要找到字符串中最长的有效括号长度，这在医学、自然语言处理等领域都有实际应用。在本文中，我们将介绍如何在Python中找到给定字符串中最长有效括号的长度。

什么是有效括号

有效括号是指一个字符串中所有左右括号匹配且不交叉的括号。例如，”()”、”()()”、”((()))”都是有效括号，而”())”、”()(“、”(()))”都不是有效括号。在实际应用中，有效括号的定义可能会略有不同，但大致相似。

解决方案

为了找到给定字符串中最长有效括号的长度，我们需要一种算法来解决这个问题。下面介绍两种常用的算法。

方法一：栈

栈是一种后进先出的数据结构，可以很方便地处理括号的匹配问题。我们可以使用栈来遍历给定字符串，同时记录所有左括号的下标。当遇到右括号时，我们从栈中弹出一个左括号的下标，然后计算当前右括号与上一个左括号之间的距离，这个距离就是有效括号的长度。我们遍历字符串的整个过程中，不断更新最长有效括号的长度即可。

下面是使用栈的Python实现：

def longest_valid_parentheses(s: str) -> int:
    stack = [-1]
    max_len = 0
    for i, c in enumerate(s):
        if c == '(':
            stack.append(i)
        else:
            if len(stack) == 1:
                stack[0] = i
            else:
                stack.pop()
                max_len = max(max_len, i - stack[-1])
    return max_len

这个函数的输入参数是一个字符串s，输出结果是给定字符串中最长有效括号的长度。这个函数使用一个栈stack来记录所有左括号的下标，同时初始化栈为[-1]。在遍历字符串s的过程中，当遇到左括号时，我们将当前下标压入栈中；当遇到右括号时，我们弹出栈顶元素。如果此时栈为空，则将右括号的下标入栈；否则，计算当前有效括号的长度，并更新最长有效括号的长度。

方法二：动态规划

动态规划是一种基于递归和分治思想的算法，常用于处理最优化问题。我们可以使用动态规划来解决这个问题。首先，我们定义一个数组dp，dp[i]表示以字符s[i]为结尾的最长有效括号的长度。显然，只有s[i]是右括号时，dp[i]才可能大于0；同时，以s[i]为结尾，最长有效括号的长度还要满足几个条件：

若s[i]是右括号，其前面必须有左括号与之匹配；

如果前面有匹配的括号，那么还需要判断其前面的那个字符是否是右括号，因为只有左右括号相邻时，才能构成有效括号。

下面是使用动态规划的Python实现：

def longest_valid_parentheses(s: str) -> int:
    n = len(s)
    dp = [0] * n
    max_len = 0
    for i in range(1, n):
        if s[i] == ')':
            if s[i-1]== '(':
                dp[i] = dp[i-2] + 2
            elif i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == '(':
                dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
            max_len = max(max_len, dp[i])
    return max_len

这个函数的输入参数和输出结果与前面栈的方法相同。这个函数使用一个数组dp来记录以每个字符结尾的最长有效括号的长度。在遍历字符串s之前，我们先初始化dp为全0。在遍历到每个字符时，如果这个字符是右括号，我们就需要计算以它为结尾的最长有效括号的长度。上面的代码中，我们使用了两个if语句来判断当前的状态，其中第一个if处理的是最简单的情况，这个字符前面只有一个左括号和一个有效括号，例如：(())。如果前面还有多个有效括号，例如：()(())，则需要执行第二个if语句。这个if语句中的dp[i-1]是当前字符之前的有效括号长度，dp[i-dp[i-1]-2]是前面所有有效括号的长度和，加上当前字符之前的左括号，就可以得到以当前字符结尾的最长有效括号的长度。

示例

下面是一个完整的示例代码，用来测试以上两个函数的效果：

def test():
    s1 = "(()"
    s2 = ")()())"
    s3 = "()(())"
    s4 = "((()))"
    s5 = "()()()()()()()"
    print(longest_valid_parentheses(s1))  # 2
    print(longest_valid_parentheses(s2))  # 4
    print(longest_valid_parentheses(s3))  # 6
    print(longest_valid_parentheses(s4))  # 6
    print(longest_valid_parentheses(s5))  # 14

test()

这个示例代码中，我们定义了5个测试用例，分别对应不同长度的字符串，然后使用两个函数进行测试，输出结果与预期结果一致。