32. Longest Valid Parentheses
难度:Hard
刷题内容
原题连接
- https://leetcode.com/problems/longest-valid-parentheses/
内容描述
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
˼·1 **- ʱ�临�Ӷ�: O(n)*- �ռ临�Ӷ�: O(n)***
��DP�ķ内容描述⡣������һ��ջȥ内容描述��ߵIJ��֣���'('��λ�ã�ֱ内容描述һ��')'ʱ���ͼ�¼ջ����'('λ�ã内容描述��ǾͿ���д��״̬ת�Ʒ��̡内容描述�dp[i]�����ַ����е�i内容描述����Զ��λ�á�����һ������')'ʱ��dp[i] = ջ��'('��λ�á����ڿ��Դ内容描述����ţ���dp[dp[i] - 1]���ڣ���dp[i] = dp[dp[i] - 1]����Ҫע��߽缴�ɡ�
class Solution {
public:
int longestValidParentheses(string s) {
int len = s.length();
if(!len)
return 0;
int dp[len];
memset(dp,-1,sizeof(dp));
int ans = 0;
vector<int> v;
for(int i = 0;i < len;++i)
if(s[i] == '(')
v.push_back(i);
else if(s[i] == ')' && v.size())
{
dp[i] = v[v.size() - 1];
if(dp[i] && dp[dp[i] - 1] >= 0)
dp[i] = dp[dp[i] - 1];
ans = max(ans,i - dp[i] + 1);
v.pop_back();
}
return ans;
}
};
