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 "()()"

(https://leetcode.com/problems/longest-valid-parentheses/description/)

动态规划算法

设dp[i] 为以s[i-1]为结尾的最长合法子串的长度,那么初始时,dp数组所有的元素都是0。

0 1 2 i n
S[0] s[1] s[2] s[i] s[n]
dp[1]=0 dp[2]=0 dp[3]=0 dp[i+1]=0 dp[n+1]=0

我们计算dp[i]时,取得s[i-1],根据s[i]的值,分情况讨论:

  1. 如果 s[i-1] == ‘(’

    由于以s[i]为结尾的子串是不合法的,所以dp[i]的值为0;
  2. 如果 s[i-1] == ‘)’

    则我们要跳过以s[i-1]结尾的最长合法子串s[j-1…i-1],长度也就是dp[i-1],j 的取值等于i - 1 - dp[i-1] - 1;然后查看s[j]字符。如果s[j]=’(’(j>0),该字符与s[i-1] 匹配,则dp[i] = dp[j] + 2 + dp[i-1]。如果 (j< 0) 或者s[j] = ‘)’,则没有以s[i-1] 为结尾的合法子串,dp[s] = 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
int maxLen = 0;
vector<int> dp(n+1,0);
for (int i=1; i<=n; i++) {
int j = i - 2 - dp[i-1];
if (s[i-1] == '(' || j < 0 || s[j] == ')')
dp[i] = 0;
else {
dp[i] = dp[i-1]+2+dp[j];
maxLen = max(maxLen, dp[i]);
}
}
return maxLen;
}
};