给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

以下是Python的实现代码：

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0
        dp = [0] * n
        res = 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] > 0 and s[i - dp[i - 1] - 1] == '(':
                    dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]
                res = max(res, dp[i])
        return res

相关问题

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。写出C语言代码

我可以回答这个问题。以下是C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int longestValidParentheses(char* s) {
int len = strlen(s);
int* dp = (int*)malloc(sizeof(int) * len);
memset(dp, , sizeof(int) * len);
int maxLen = ;
for (int i = 1; i < len; i++) {
if (s[i] == ')') {
if (s[i - 1] == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : ) + 2;
} else if (i - dp[i - 1] > && s[i - dp[i - 1] - 1] == '(') {
dp[i] = dp[i - 1] + ((i - dp[i - 1] >= 2) ? dp[i - dp[i - 1] - 2] : ) + 2;
}
maxLen = maxLen > dp[i] ? maxLen : dp[i];
}
}
free(dp);
return maxLen;
}

int main() {
char s[] = "(()())";
printf("%d\n", longestValidParentheses(s));
return ;
}

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

我可以回答这个问题。这个问题可以使用栈来解决。我们可以遍历字符串，如果遇到左括号，就将其下标入栈；如果遇到右括号，就将栈顶元素出栈，表示匹配成功，计算当前子串长度。如果栈为空，表示当前右括号没有匹配的左括号，将当前右括号下标入栈，继续遍历。最后栈中剩余的下标表示没有匹配的左括号，我们可以根据相邻下标之间的距离计算最长有效括号子串的长度。