LeetCode [32] 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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

class Solution { public: int longestValidParentheses(string s) { int n = s.size(), ret = 0; vector<int> dp(n);//dp[i] is the length of valid str ending at i for(int i=0; i<n; ++i) { if(i>0 && s[i]==')'){ int j = i - dp[i-1] - 1; if(j>=0 && s[j]=='('){ dp[i] = dp[i-1]+2; if(j-1>=0) dp[i] += dp[j-1]; } ret = max(ret, dp[i]); } } return ret; } };