32. Longest Valid Parentheses

你快乐吗

Posted by bbkgl on February 19, 2020

浮云出处元无定

得似浮云也自由

C++,dp,字符串。这道题也有不用dp的解法,但是这种奇技淫巧并不通用,到面试的时候很难想起来,还是老老实实把dp理解好,能够解很多题目。

本题目如果用动态规划,重点是把括号匹配的关系理清楚:

  • (在前,)在后
  • 如果()之间是(...)(...)有效括号序列,那么...一定由0到多个不定长度的有效括号序列组成

理清括号匹配的关系后,再思考怎么用dp去套。。。

显然,我们可以用dp[i][j] == true来表示[i, j]有效括号序列,但实际上不用二维数组,一维就够了,dp[i][j] == true记录了两个信息

  • ij的长度,即j - i + 1
  • ij之间,符合有效括号序列

这两个信息,用一维数组即可记录,dp[i] = n,表示以i为结尾的长为n有效括号序列。那么当碰到某个字符是)的时候,需要找到与之匹配且没有被匹配的(

  • dp[i - 1]记录的就是以i为结尾的长为n最长有效括号序列
  • i - dp[i - 1] - 1就是与之匹配且没有被匹配的(所在的位置

所以长度就是:dp[i] = (i - j + 1) + ((j - 1) >= 0 ? dp[j - 1] : 0)

代码也是很简短:

class Solution {
public:
    int longestValidParentheses(string s) {
        int ans = 0;
        vector<int> dp(s.length(), 0);
        for (int i = 1; i < s.length	(); i++) {
            if (s[i] == ')') {
                int j = i - dp[i - 1] - 1;
                if (j >= 0 && s[j] == '(') 
                    dp[i] = (i - j + 1) + ((j - 1) >= 0 ? dp[j - 1] : 0);
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};