LeetCode——32. Longest Valid Parentheses(C++)

LeetCode——32. Longest Valid Parentheses(C++)
Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: s = “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”.

Example 2:
Input: s = “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”.

Example 3:
Input: s = “”
Output: 0

Constraints:
0 <= s.length <= 3 * 104
s[i] is ‘(’, or ‘)’.

解题思路：
动态规划，dp[i]存储以i为终点时，此处往前有几个连续对子，
从0开始遍历，所有‘（’的对应的dp数组值为0，遇到‘）’则考察其往前可配对的情况，前一个为‘（’则其dp值为前前一个的dp值+2（相关边界情况见代码），前一个为‘）’则考察此‘）’的dp值，非零则进行进一步计算，为零则当前dp也为零；
代码：

class Solution {
public:
    int longestValidParentheses(string s) {
        int siz=s.size();
        vector<int>dp;
        dp.resize(siz,0);
        int maxsiz=0;    //记录最大的配对数
        for(int i=0;i<siz;i++)
        {
            if(i&&s[i]==')')
            {
                if(s[i-1]=='(')
                {
                    if(i>2)dp[i]=2+dp[i-2];
                    else dp[i]=2;
                    if(maxsiz<dp[i])maxsiz=dp[i];
                }
                else if(s[i-1]==')'&&dp[i-1])
                {
                    if(i-1-dp[i-1]>=0&&s[i-1-dp[i-1]]=='(')
                    {
                        if(i-1-dp[i-1]==0)
                        dp[i]=dp[i-1]+2;
                        else
                          dp[i]=dp[i-1]+2+dp[i-1-dp[i-1]-1];  
                        if(maxsiz<dp[i])maxsiz=dp[i];
                    }
                }
            }
        }
        return maxsiz;
    }
};

submission:

最后

以上就是失眠羊为你收集整理的LeetCode——32. Longest Valid Parentheses(C++)的全部内容，希望文章能够帮你解决LeetCode——32. Longest Valid Parentheses(C++)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。