LeetCode 32. Longest Valid Paren

Longest Valid Parentheses

题目

给定一个字符串s，由 '(' 和 ')' 组成，求最长合法括号(valid parentheses)长度

例

"((()())("，合法段为"(()())"，长度为6

解法

这种求最长xxx的题目很容易想到动态规划，使用一个数组vector<int> dp记录 由s[i]作为最后一个字符的字符串的substring的长度

例

"((()())(": [0, 0, 0, 2, 0, 4, 6, 0]

每个字符s[i]的情况如下

• '(':
  dp[i] = 0 // '(' 不可能是任意一个合法括号的结尾
  不需要操作，因为初始为0
• ')':
  最长长度增加2，因为增加了一组括号"()"，但在哪个substring的基础上增加2需要继续讨论
  1. s[i - 1] == '(': 直接在dp[i - 1]的基础上增加2
  2. • s[i - 1] == ')': 这个情况比较复杂，s[i - 1]可能是一个合法括号组合的结尾，我们需要找出以s[i - 1]为结尾的substring之前的那个元素，
  • s[i - 1] == '(': 该 '(' 与s[i] 包括这两个元素之间的元素组成了一个更长的valid parentheses(下面写如何找出这个元素)。如果在这个新的substring之前也是valid parentheses，那么新的长度也需要加上这个前面的substring长度(dp[i - 1 - dp[i - 1]])
    ')': 不是valid parentheses，不用理他

如何找出这个元素

dp[i - 1] 记录了 s[i]之前的substring的长度，用i - 1减去长度就得到了我们要找的那个元素

s: "( ( ) ( ) )"
dp: [0, 0, 2, 0, 2, 0]
i = 5: s[i] == ')', s[i - 1] = ')' 我们要找找出以s[i - 1]结尾的substring之前的那个元素也就是s[0], 也就是s[i - 1 - dp[i - 1]];
// 不要忘记检查位序是否合法

代码

class Solution {
public:
    int longestValidParentheses(string s) {
        if (s.size() < 2) return 0;
        vector<int> dp(s.size(), 0);
        int max_len = 0;
        for (int i = 1; i < s.size(); i++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = ((i >= 2) ? dp[i - 2] : 0) + 2;
                    max_len = max(max_len, dp[i]);
                } else {
                    // dp[i - 1] == ')'
                    if ((i - 1 - dp[i - 1]) >= 0 and s[i - 1 - dp[i - 1]] == '(') {
                        dp[i] = dp[i - 1] + 2 + ((i - 1 - dp[i - 1] >= 2) ? dp[i - 2 - dp[i - 1]] : 0);
                        max_len = max(max_len, dp[i]);
                    }
                }
            }
        }
        return max_len;
    }
};