0032._Longest_Valid_Parentheses.md

32. Longest Valid Parentheses

难度:Hard

刷题内容

原题连接

• https://leetcode.com/problems/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 - 时间复杂度: O(n)- 空间复杂度: O(n)******

用DP的方法解这题。首先用一个栈去储存括号左边的部分，即'('的位置，直到遇到第一个')'时。就记录栈顶的'('位置，接下来我们就可以写出状态转移方程。定义数组dp[i]代表字符串中第i个括号向左最远的位置。当第一次遇到')'时，dp[i] = 栈顶'('的位置。由于可以存在连续的括号，若dp[dp[i] - 1]存在，则dp[i] = dp[dp[i] - 1]，需要注意边界即可。

class Solution {
public:
    int longestValidParentheses(string s) {
        int len = s.length();
        if(!len)
            return 0;
        int dp[len];
        memset(dp,-1,sizeof(dp));
        int ans = 0;
        vector<int> v;
        for(int i = 0;i < len;++i)
            if(s[i] == '(')
                v.push_back(i);
            else if(s[i] == ')' && v.size())
            {
                dp[i] = v[v.size() - 1];
                if(dp[i] && dp[dp[i] - 1] >= 0)
                    dp[i] = dp[dp[i] - 1];
                ans = max(ans,i - dp[i] + 1);
                v.pop_back();
            }
        return ans;
    }
};