给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。写出C语言代码
时间: 2023-03-28 08:03:03 浏览: 84
我可以回答这个问题。以下是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 ;
}
阅读全文