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;
    }
};