顿搜
飞过闲红千叶，夕岸在哪
类目归类
[LeetCode 32] Longest Valid Parentheses [C] [Runtime : 6 MS]
06/12
1. Description
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
2. Runtime Distribution
3. Submission Details
4. Example
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
5. Explanation
- If s[i] is '(', dp[i] = 0 //because any string end with '(' cannot be a valid one.
- If s[i] is ')'
- If s[i-1] == '(', dp[i] = dp[i-2] + 2
- if s[i-1] == ')' && s[i-dp[i-1]-1] == '(', dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]
6. Code
#include<stdio.h>
#include <string.h>
#include <stdlib.h>
int longestValidParentheses(char* s) {
int length = strlen(s);
if(length <= 1)
{
return 0;
}
int result = 0;
int* dp = (int *)malloc(length * sizeof(int));
dp[0] = 0;
for(int i = 1; i < length; i++)
{
if(s[i] ==')' && i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(')
{
dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
result = dp[i] > result ? dp[i] : result;
}else
{
dp[i] = 0;
}
}
return result;
}
int main()
{
char * s = ")()())";
printf("%d\n", longestValidParentheses(s));
system("pause");
return 0;
}
